SpringerLink
Log in

An effective immune algorithm based on novel dispatching rules for the flexible flow-shop scheduling problem with multiprocessor tasks

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

Abstract

As a strongly NP-hard problem, the flexible flow-shop problem with multiprocessor tasks (FFSPMT) has gained much attention due to its academic significance and wide application background. To solve the FFSPMT, the dispatching rule is crucial to decode job order sequences to schedules, which has a great effect on the quality of the solution. In this paper, several novel dispatching rules are proposed to arrange the job processing order and machine assignment to minimize makespan of the FFSPMT by narrowing the idle time between the consecutive operations in the processor as well as by increasing the flexibility in selecting processors to schedule the following operations. With these rules, an immune algorithm (IA) is proposed to solve the FFSPMT, where special crossover, mutation, and vaccination operators are well designed and utilized. Meanwhile, some theoretical analysis for the local search operators is provided for guiding local search reasonably. The computational results based on 120 well-known benchmark instances and comparisons with some existing algorithms demonstrate the effectiveness of the proposed dispatching rules and the immune algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ruiz R, Vázquez-Rodríguez JA (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205(1):1–18

    Article  MATH  Google Scholar 

  2. Alaykýran K, Engin O, Döyen A (2007) Using ant colony optimization to solve hybrid flow shop scheduling problems. Int J Adv Manuf Technol 35(5):541–550

    Article  Google Scholar 

  3. Gholami M, Zandieh M, Alem-Tabriz A (2009) Scheduling hybrid flow shop with sequence-dependent setup times and machines with random breakdowns. Int J Adv Manuf Technol 42(1):189–201

    Article  Google Scholar 

  4. Rashidi E, Jahandar M, Zandieh M (2010) An improved hybrid multi-objective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines. Int J Adv Manuf Technol 49(9):1129–1139

    Article  Google Scholar 

  5. Drozdowski M (1996) Scheduling multiprocessor tasks—an overview. Eur J Oper Res 94(2):215–230

    Article  MATH  Google Scholar 

  6. Guan Y, **ao WQ, Cheung RK, Li CL (2002) A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis. Oper Res Lett 30(5):343–350

    Article  MathSciNet  MATH  Google Scholar 

  7. Oĝuz C, Zinder Y, Ha Do V, Janiak A, Lichtenstein M (2004) Hybrid flow-shop scheduling problems with multiprocessor task systems. Eur J Oper Res 152(1):115–131

    Article  MATH  Google Scholar 

  8. Brucker P, Schlie R (1990) Job-shop scheduling with multi-purpose machines. Computing 45(4):369–375

    Article  MathSciNet  MATH  Google Scholar 

  9. Ercan MF, Oğuz C (2005) Performance of local search heuristics on scheduling a class of pipelined multiprocessor tasks. Comput Electr Eng 31(8):537–555

    Article  MATH  Google Scholar 

  10. Bertel S, Billaut JC (2004) A genetic algorithm for an industrial multiprocessor flow shop scheduling problem with recirculation. Eur J Oper Res 159(3):651–662

    Article  MathSciNet  MATH  Google Scholar 

  11. Kahraman C, Engin O, Kaya İ, Öztürk RE (2010) Multiprocessor task scheduling in multistage hybrid flow-shops: a parallel greedy algorithm approach. Appl Soft Comput 10(4):1293–1300

    Article  Google Scholar 

  12. Chen J, Lee CY (1999) General multiprocessor task scheduling. Nav Res Logist 46(1):57–74

    Article  MathSciNet  MATH  Google Scholar 

  13. Lee CY, Cai X (1999) Scheduling one and two-processor tasks on two parallel processors. IIE Trans 31(5):445–455

    Google Scholar 

  14. Krawczyk H, Kubale M (1985) An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Trans Comput 100(9):869–872

    Article  Google Scholar 

  15. Oĝuz C, Ercan MF (2005) A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. J Sched 8(4):323–351

    Article  MathSciNet  MATH  Google Scholar 

  16. Błażewicz J, Dell’Olmo P, Drozdowski M, Speranza MG (1992) Scheduling multiprocessor tasks on three dedicated processors. Inf Process Lett 41(5):275–280

    Article  MATH  Google Scholar 

  17. Brucker P, Knust S, Roper D, Zinder Y (2000) Scheduling UET task systems with concurrency on two parallel identical processors. Math Meth Op Res 52(3):369–387

    Article  MathSciNet  MATH  Google Scholar 

  18. Lloyd EL (1981) Concurrent task systems. Oper Res 29(1):189–201

    Article  MathSciNet  MATH  Google Scholar 

  19. Du J, Joseph YTL (1989) Complexity of scheduling parallel task systems. SIAM J Discret Math 2:473

    Article  MATH  Google Scholar 

  20. Chen T, Wang YC (2009) A nonlinear scheduling rule incorporating fuzzy-neural remaining cycle time estimator for scheduling a semiconductor manufacturing factory—a simulation study. Int J Adv Manuf Technol 45(1):110–121

    Article  Google Scholar 

  21. Jeang A, Chen T, Li HC, Liang F (2007) Simultaneous process mean and process tolerance determination with adjustment and compensation for precision manufacturing process. Int J Adv Manuf Technol 33(11):1159–1172

    Article  Google Scholar 

  22. Chen T (2010) Intelligent scheduling approaches for a wafer fabrication factory. J Intel Manu 23(3):897–911

    Article  Google Scholar 

  23. Gupta JND (1988) Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc 39(4):359–364

    MATH  Google Scholar 

  24. Gupta JND, Tunc E (1998) Minimizing tardy jobs in a two-stage hybrid flowshop. Int J Prod Res 36(9):2397–2417

    Article  MATH  Google Scholar 

  25. Haouari M, M’Hallah R (1997) Heuristic algorithms for the two-stage hybrid flowshop problem. Oper Res Lett 21(1):43–53

    Article  MathSciNet  MATH  Google Scholar 

  26. Riane F, Artiba A, Elmaghraby SE (1998) A hybrid three-stage flowshop problem: efficient heuristics to minimize makespan. Eur J Oper Res 109(2):321–329

    Article  MATH  Google Scholar 

  27. Oĝuz C, Fikret Ercan M, Edwin Cheng T, Fung Y (2003) Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop. Eur J Oper Res 149(2):390–403

    Article  MATH  Google Scholar 

  28. Oĝuz C, Fikret Ercan M (1997) Scheduling multiprocessor tasks in a two-stage flow-shop environment. Comput Ind Eng 33(1–2):269–272

    Google Scholar 

  29. Ulusoy G (2004) Multiprocessor task scheduling in multistage hybrid flow-shops: a genetic algorithm approach. J Oper Res Soc 55(5):504–512

    Article  MATH  Google Scholar 

  30. Ying KC, Lin SW (2006) Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach. Int J Prod Res 44(16):3161–3177

    Article  MATH  Google Scholar 

  31. Tseng CT, Liao CJ (2008) A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Int J Prod Res 46(17):4655–4670

    Article  MATH  Google Scholar 

  32. Wang HM, Chou FD, Wu FC (2010) A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan. Int J Adv Manuf Technol 53(5–8):761–776

    Google Scholar 

  33. Chen T (2011) A dynamically optimized fluctuation smoothing rule for scheduling jobs in a wafer fabrication factory. Int J Intell Inf Technol 7(4):47–64

    Article  Google Scholar 

  34. Chen T, Wang YC, Lin YC (2010) A bi-criteria four-factor fluctuation smoothing rule for scheduling jobs in a wafer fabrication factory. Int J Inno Comp Info Cont 6(10):4289–4303

    Google Scholar 

  35. Wang L, Xu Y, Zhou G, Wang S, Liu M (2012) A novel decoding method for the hybrid flow-shop scheduling problem with multiprocessor tasks. Int J Adv Manuf Technol 59(9–12):1113–1125

    Article  Google Scholar 

  36. Tavakkoli-Moghaddam R, Rahimi-Vahed A, Mirzaei A (2008) Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm. Int J Adv Manuf Technol 36(9):969–981

    Article  Google Scholar 

  37. Graham RL, Lawler EL, Lenstra JK, Kan AHGR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Disc Math 5(2):287–326

    Article  MATH  Google Scholar 

  38. Wang L, Zheng D (2003) An effective hybrid heuristic for flow shop scheduling. Int J Adv Manuf Technol 21:38–44

    Article  Google Scholar 

  39. Wang X, Gao L, Zhang C, Shao X (2010) A multi-objective genetic algorithm based on immune and entropy principle for flexible job-shop scheduling problem. Int J Adv Manuf Technol 51(5):757–767

    Article  Google Scholar 

  40. Wang L, Zhou G, Xu Y, Wang SY (2012) An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Technol 60(1):303–315

    Article  Google Scholar 

  41. Chun JS, Kim MK, Jung HK, Hong SK (1997) Shape optimization of electromagnetic devices using immune algorithm. IEEE Trans Magn 33(2):1876–1879

    Article  Google Scholar 

  42. Oĝuz C (2006) Data for hybrid flow shop scheduling with multiprocessor tasks, KOC University. Available at http://home.ku.edu.tr/~coguz

  43. Singh MR, Mahapatra SS (2012) A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks. Int J Adv Manuf Technol 62(1):266–277

    Google Scholar 

  44. Engin O, Ceran G, Yilmaz MK (2011) An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems. Appl Soft Comput 11(3):3056–3065

    Article  Google Scholar 

  45. Montgomery DC (2008) Design and analysis of experiments. Wiley, New York

    Google Scholar 

  46. Wang L, Zhou G, Xu Y, Liu M (2012) An enhanced Pareto-based artificial bee colony algorithm for the multi-objective flexible job-shop scheduling. Int J Adv Manuf Technol 60(9):1111–1123

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Tsinghua National Laboratory for Information Science and Technology (TNList), Department of Automation, Tsinghua University, Bei**g, 100084, China

    Ye Xu, Ling Wang, Shengyao Wang & Min Liu

Authors
  1. Ye Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ling Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shengyao Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Min Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ye Xu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xu, Y., Wang, L., Wang, S. et al. An effective immune algorithm based on novel dispatching rules for the flexible flow-shop scheduling problem with multiprocessor tasks. Int J Adv Manuf Technol 67, 121–135 (2013). https://doi.org/10.1007/s00170-013-4759-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-013-4759-6

Keywords

Search

Navigation