Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Multi-objective no-wait flow-shop scheduling with a memetic algorithm based on differential evolution

  • Focus
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

In this paper, a memetic algorithm (MA) based on differential evolution (DE), namely MADE, is proposed for the multi-objective no-wait flow-shop scheduling problems (MNFSSPs). Firstly, a largest-order-value rule is presented to convert individuals in DE from real vectors to job permutations so that the DE can be applied for solving flow-shop scheduling problems (FSSPs). Secondly, the DE-based parallel evolution mechanism is applied to perform effective exploration, and several local searchers developed according to the landscape of multi-objective FSSPs are applied to emphasize local exploitation. Thirdly, a speed-up computing method is developed based on the property of the no-wait FSSPs. In addition, the concept of Pareto dominance is used to handle the updating of solutions in sense of multi-objective optimization. Due to the well balance between DE-based global search and problem-dependent local search as well as the utilization of the speed-up evaluation, the MNFSSPs can be solved effectively and efficiently. Simulation results and comparisons demonstrate the effectiveness and efficiency of the proposed MADE.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Aldowaisan T, Allahverdi A (2003) New heuristics for no-wait flowshops to minimize makespan. Comput Oper Res 30: 1219–1231

    Article  MATH  Google Scholar 

  • Allahverdi A, Aldowaisan T (2004) No-wait flowshops with bicriteria of makespan and maximum lateness. Eur J Oper Res 152: 132–147

    Article  MATH  MathSciNet  Google Scholar 

  • Arroyo JEC, Armentano VA (2005) Genetic local search for multi-objective flowshop scheduling problems. Eur J Oper Res 167: 717–738

    Article  MATH  MathSciNet  Google Scholar 

  • Baker KR (1974) Introduction to sequencing and scheduling. Wiley, New York

    Google Scholar 

  • Bean JC (1994) Genetic algorithm and random keys for sequencing and optimization. ORSA J Comput 6(2): 154–160

    MATH  Google Scholar 

  • Bonney MC, Gundry SW (1976) Solutions to the constrained flowshop sequencing problem. Oper Res Quart 24: 869–883

    Article  Google Scholar 

  • Caponio A, Cascella GL, Neri F, Salvatore N, Sumner M (2007) A fast adaptive memetic algorithm for online and offline control design of PMSM drives. IEEE T Syst Man Cybern B 37(1): 28–41

    Article  Google Scholar 

  • Carlier J (1978) Ordonnancements a contraintes disjonctives. R.A.I.R.O. Recherche operationelle/Oper Res 12: 333–351

    MATH  MathSciNet  Google Scholar 

  • Chang YP, Wu CJ (2005) Optimal multiobjective planning of large-scale passive harmonic filters using hybrid differential evolution method considering parameter and loading uncertainty. IEEE T Power Deliver 20(1): 408–416

    Article  Google Scholar 

  • Chen CL, Neppalli RV, Aljaber N (1996) Genetic algorithms applied to the continuous flow-shop problem. Comput Ind Eng 30: 919–929

    Article  Google Scholar 

  • Czyzak P, Jaszkiewicz A (1998) Pareto-simulated annealing—a metaheuristic technique for multi-objective combinatorial optimization. J Multi-Crit Decis Anal 7(1): 34–47

    Article  MATH  Google Scholar 

  • Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE T Evol Comput 6(2): 182–197

    Article  Google Scholar 

  • Dimopoulos C, Zalzala AMS (2000) Recent development in evolutionary computation for manufacturing optimization: problems, solutions, and comparisons. IEEE T Evolut Comput 4: 93–113

    Article  Google Scholar 

  • Feoktistov V (2006) Differential evolution: in search of solutions. Springer, Heidelberg

    MATH  Google Scholar 

  • Gangadharan R, Rajendran C (1993) Heuristic algorithms for scheduling in the no-wait flowshop. Int J Prod Econ 32((3): 285–290

    Article  Google Scholar 

  • Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of np-completeness. Freeman, San Francisco

    MATH  Google Scholar 

  • Geiger MJ (2007) On operators and search space topology in multi-objective flow-shop scheduling. Eur J Oper Res 181(1): 195–206

    Article  MATH  MathSciNet  Google Scholar 

  • Grabowski J, Pempera J (2005) Some local search algorithms for no-wait flow-shop problem with makespan criterion. Comput Oper Res 32: 2197–2212

    Article  MATH  MathSciNet  Google Scholar 

  • Hart WE, Krasnogor N, Smith JE (2004) Recent advances in memetic algorithms. Springer, Heidelberg

    Google Scholar 

  • Hall NG, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 44: 510–525

    Article  MATH  MathSciNet  Google Scholar 

  • Heller J (1960) Some numerical experiments for an M × J flow-shop and its decision-theoretical aspects. Oper Res 8: 178–184

    Article  MATH  MathSciNet  Google Scholar 

  • Ilonen J, Kamarainen JK, Lampinen J (2003) Differential evolution training algorithm for feed-forward neural networks. Neural Process Lett 17(1): 93–105

    Article  Google Scholar 

  • Ishibuchi H, Murata T (1998) A multiobjective genetic local search algorithm and its application to flowshop scheduling. IEEE T Syst Man Cybern C 28(3): 392–403

    Article  Google Scholar 

  • Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE T Evol Comput 7: 204–223

    Article  Google Scholar 

  • Jaszkiewicz A (2002) Genetic local search for multi-objective combinatorial optimization. Eur J Oper Res 137(1): 50–71

    Article  MATH  MathSciNet  Google Scholar 

  • Jaszkiewicz A (2003) Do multiple-objective metaheuristcs deliver on their promises? A computational experiment on the set-covering problem. IEEE T Evolut Comput 7(2): 133–143

    Article  MathSciNet  Google Scholar 

  • Jonathan EF, Richard ME, Sameer S (2003) Using unconstrained elite archives for multiobjective optimization. IEEE T Evolut Comput 7(3): 305–323

    Article  Google Scholar 

  • King JR, Spachis AS (1980) Heuristics for flowshop scheduling. Int J Prod Res 18: 343–357

    Google Scholar 

  • Knowles JD, Corne DW (2002) On metrics for comparing nondominated sets. In: 2002 Congress on Evolutionary Computation, Honolulu, HI, USA, pp 711–716

  • Kumar S, Bagchi TP, Sriskandarajah C (2000) Lot streaming and scheduling heuristics for m-machine no-wait flowshops. Comput Ind Eng 38: 149–172

    Article  Google Scholar 

  • Liu B, Wang L, Jin YH (2007) An effective hybrid particle swarm optimization for no-wait flow-shop scheduling. Int J Adv Manuf Tech 31(9–10): 1001–1011

    Article  Google Scholar 

  • Murata T, Ishibuchi H, Tanaka H (1996) Genetic algorithms for flowshop scheduling problems. Comput Ind Eng 30: 1061–1071

    Article  Google Scholar 

  • Nearchou AC (2008) A differential evolution approach for the common due date early/tardy job scheduling problem. Comput Oper Res 35: 1329–1343

    Article  MATH  Google Scholar 

  • Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24: 1097–1100

    Article  MATH  MathSciNet  Google Scholar 

  • Nearchou AC, Omirou SL (2006) Differential evolution for sequencing and scheduling optimization. J Heuristics 12(6): 395–411

    Article  Google Scholar 

  • Neri F, Toivanen J, Cascella GL, Ong YS (2007) An adaptive multimeme algorithm for designing HIV multidrug therapies. IEEE ACM T Comput BI 4(2): 264–278

    Google Scholar 

  • Nowicki E, Smutnicki C (2006) Some aspects of scatter search in the flow-shop problem. Eur J Oper Res 169: 654–666

    Article  MATH  MathSciNet  Google Scholar 

  • Ong YS, Keane AJ (2004) Meta-Lamarckian learning in memetic algorithms. IEEE T Evol Comput 8: 99–110

    Article  Google Scholar 

  • Ong YS, Lim MH, Zhu N, Wong KW (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE T Syst Man Cy B 36(1): 141–152

    Article  Google Scholar 

  • Onwubolu G, Davendra D (2006) Scheduling flow-shops using differential evolution algorithm. Eur J Oper Res 171(2): 674–692

    Article  MATH  Google Scholar 

  • Pinedo M (2002) Scheduling: theory, algorithms and systems, 2nd edn. Prentice-Hall, NJ

    MATH  Google Scholar 

  • Price K, Storn R (2007) Differential evolution (DE) for continuous function optimization. http://www.icsi.berkeley.edu/%7Estorn/code.html. Accessed 13 July 2007

  • Price K, Storn R, Lampinen J (2005) Differential evolution: a practical approach to global optimization. Springer, Berlin, pp 227–238

  • Qian B, Wang L, Huang DX, Wang X (2008) Scheduling multi-objective job shops using a memetic algorithm based on differential evolution. Int J Adv Manuf Technol 35: 1014–1027

    Article  Google Scholar 

  • Qian B, Wang L, Huang DX, Wang WL, Wang X (2009) An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Comput Oper Res 36(1): 209–233

    Article  MATH  MathSciNet  Google Scholar 

  • Rajendran C (1994) A no-wait flowshop scheduling heuristic to minimize makespan. J Oper Res Soc 45(4): 472–478

    Article  MATH  Google Scholar 

  • Reeves CR (1995) A genetic algorithm for flowshop sequencing. Comput Oper Res 22: 5–13

    Article  MATH  Google Scholar 

  • Reeves CR (1999) Landscapes, operations and heuristic search. Ann Oper Res 86: 473–490

    Article  MATH  MathSciNet  Google Scholar 

  • Reeves CR, Yamada T (1998) Genetic algorithms, path relinking and the flowshop sequencing problem. Evol Comput 6: 45–60

    Article  Google Scholar 

  • Schiavinotto T, Stützle T (2007) A review of metrics on permutations for search landscape analysis. Comput Oper Res 34(10): 3143–3153

    Article  MATH  Google Scholar 

  • Stadtler H (2005) Supply chain management and advanced planning-basics, overview and challenges. Eur J Oper Res 163: 575–588

    Article  MATH  Google Scholar 

  • Storn R, Price K (1997) Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. J Glob Optim 11(4): 341–359

    Article  MATH  MathSciNet  Google Scholar 

  • Tasgetiren MF, Liang YC, Sevkli M, Gencyilmaz G (2004) Differential evolution algorithm for permutation flowshop sequencing problem with makespan criterion. In: Proceedings of 4th international symposium on intelligent manufacturing systems, Sakarya, Turkey, pp 442–452

  • Tang J, Lim MH, Ong YS (2007) Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput 11(9): 873–888

    Article  Google Scholar 

  • Tavakkoli-Moghaddam R, Rahimi-Vahed A, Hossein Mirzaei A (2007) A hybrid multi-objective immune algorithm for a flow shop scheduling problem with bi-objectives: weighed mean completion time and weighted mean tardiness. Inf Sci. doi:10.1016/j.ins.2007.06.001

  • Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64: 278–285

    Article  MATH  Google Scholar 

  • Van Deman JM, Baker KR (1974) Minimizing mean flow time in the flowshop with no intermediate queues. AIIE Trans 6: 28–34

    Google Scholar 

  • Wang L (2003) Shop scheduling with genetic algorithms. Tsinghua Univ. Press & Springer, Beijing

    Google Scholar 

  • Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE T Evol Comput 1: 67–82

    Article  Google Scholar 

  • Zhou Z, Ong YS, Lim MH, Lee BS (2007) Memetic algorithm using multi-surrogates for computationally expensive optimization problems. Soft Comput 11(10): 957–971

    Article  Google Scholar 

  • Zhu Z, Ong YS, Dash M (2007) Wrapper-filter feature selection algorithm using a memetic framework. IEEE T Syst Man Cybern B 37(1): 70–76

    Article  Google Scholar 

  • Zitzler E, Thiele L (1999) Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE T Evolut Comput 3(4): 257–271

    Article  Google Scholar 

  • Zitzler E, Deb K, Thiele L (2000) Comparison of multiobjective evolutionary algorithms: Empirical results. IEEE T Evol Comput 8(2): 173–195

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Automation, Tsinghua University, Beijing, 100084, People’s Republic of China

    Bin Qian, Ling Wang, De-Xian Huang & Xiong Wang

  2. Department of Automation, Kunming University of Science and Technology, Kunming, 650051, People’s Republic of China

    Bin Qian

Authors
  1. Bin Qian
    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. De-Xian Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xiong Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bin Qian.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Qian, B., Wang, L., Huang, DX. et al. Multi-objective no-wait flow-shop scheduling with a memetic algorithm based on differential evolution. Soft Comput 13, 847–869 (2009). https://doi.org/10.1007/s00500-008-0350-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-008-0350-8

Keywords

Search

Navigation