Abstract
The permutation flow shop problem is a complex combinatorial optimization problem. Over the last few decades, a good number of algorithms have been proposed to solve static permutation flow shop problems. However, in practice, permutation flow shop problems are not static but rather are dynamic because the orders (where each order contains multiple jobs) arrive randomly for processing and the operation of any job may be interrupted due to resource problems. For any interruption, it is necessary to reschedule the existing jobs that are under process at different stages in the production system and also any orders that were previously accepted that are waiting for processing. In this paper, a memetic algorithm-based rescheduling approach has been proposed to deal with both single and multiple orders while considering random interruptions of resources. The experimental results have shown that the performance of the proposed approach is superior to traditional reactive approaches.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abumaizar RJ, Svestka JA (1997) Rescheduling job shops under random disruptions. Int J Prod Res 35:2065–2082
Pinedo M (2012) Scheduling: theory, algorithms, and systems, 4th edn. Springer, New York
Aggoune R, Portmann M-C (2006) Flow shop scheduling problem with limited machine availability: a heuristic approach. Int J Prod Econ 99:4–15
Schmidt G (2000) Scheduling with limited machine availability. Eur J Oper Res 121:1–15
Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64:278–285
Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Nav Res Logist Q 1:61–68
Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117–129
Bansal S (1977) Minimizing the sum of completion times of n jobs over m machines in a flowshop—a branch and bound approach. AIIE T 9:306–311
Selen WJ, Hott DD (1986) A mixed-integer goal-programming formulation of the standard flow-shop scheduling problem. J Oper Res Soc 37:1121–1128
Nawaz M, Enscore EE, Ham I (1983) A heuristic algorithm for the M-machine, N-job flowshop sequencing problem. OMEGA Int J Manag Sci 11:91–95
Grabowski J, Wodecki M (2004) A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Comput Oper Res 31:1891–1909
Tasgetiren MF, Liang YC, Sevkli M, Gencyilmaz G (2007) A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. Eur J Oper Res 177:1930–1947
Osman IH, Potts CN (1989) Simulated annealing for permutation flowshop scheduling. OMEGA Int J Manag Sci 17:551–557
Zobolas GI, Tarantilis CD, Ioannou G (2009) Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm. Comput Oper Res 36:1249–1267
Rajendran C, Ziegler H (2004) Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur J Oper Res 155:426–438
Ruiz R, Maroto C (2005) A comprehensive review and evaluation of permutation flowshop heuristics. Eur J Oper Res 165:479–494
Ruiz R, Maroto C, Alcaraz J (2006) Two new robust genetic algorithms for the flowshop scheduling problem. OMEGA Int J Manag Sci 34:461–476
Rahman HF, Sarker RA, Essam DL (2013) A memetic algorithm for permutation flow shop problems, in 2013 IEEE Congress on Evolutionary Computation (CEC), pp. 1618–1625
Dasgupta P, Das S (2015) A discrete inter-species cuckoo search for flowshop scheduling problems. Comput Oper Res 60:111–120
Slotnick SA (2011) Order acceptance and scheduling: a taxonomy and review. Eur J Oper Res 212:1–11
Slotnick SA, Morton TE (1996) Selecting jobs for a heavily loaded shop with lateness penalties. Comput Oper Res 23:131–140
Lewis HF, Slotnick SA (2002) Multi-period job selection: planning work loads to maximize profit. Comput Oper Res 29:1081–1098
Slotnick SA, Morton TE (2007) Order acceptance with weighted tardiness. Comput Oper Res 34:3029–3042
Rom WO, Slotnick SA (2009) Order acceptance using genetic algorithms. Comput Oper Res 36:1758–1767
Wester F, Wijngaard J, ZIJM WRM (1992) Order acceptance strategies in a production-to-order environment with setup times and due-dates. Int J Prod Res 30:1313–1326
Duenyas I, Hopp WJ (1995) Quoting customer lead times. Manag Sci 41:43–57
Duenyas I (1995) Single facility due date setting with multiple customer classes. Manag Sci 41:608–619
Nandi A, Rogers P (2004) Using simulation to make order acceptance/rejection decisions. SIMULATION 80:131–142
Rogers P, Nandi A (2007) Judicious order acceptance and order release in make-to-order manufacturing systems. Prod Plan Control 18:610–625
Moreira MRA, Alves RAFS (2009) A methodology for planning and controlling workload in a job-shop: a four-way decision-making problem. Int J Prod Res 47:2805–2821
Ouelhadj D, Petrovic S (2009) A survey of dynamic scheduling in manufacturing systems. J Sched 12:417–431
Stoop PPM, Wiers VCS (1996) The complexity of scheduling in practice. Int J Oper Prod Manag 16:37–53
Suresh V, Chaudhuri D (1993) Dynamic scheduling-a survey of research. Int J Prod Econ 32:53–63
Vieira GE, Herrmann JW, Lin E (2003) Rescheduling manufacturing systems: a framework of strategies, policies, and methods. J Sched 6:39–62
Tang LX, Zhao Y, Liu JY (2014) An improved differential evolution algorithm for practical dynamic scheduling in steelmaking-continuous casting production. IEEE Trans Evol Comput 18:209–225
McKay KN, Buzacott JA, Safayeni FR (1989) The scheduler’s knowledge of uncertainty: the missing link, Knowledge Based Production Management Systems, pp. 171–189
Adiri I, Frostig E, Kan AHGR (1991) Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs. Nav Res Logist 38:261–271
Liao CJ, Chen WJ (2004) Scheduling under machine breakdown in a continuous process industry. Comput Oper Res 31:415–428
Hall NG, Potts CN (2004) Rescheduling for new orders. Oper Res 52:440–453
Yang B (2007) Single machine rescheduling with new jobs arrivals and processing time compression. Int J Adv Manuf Technol 34:378–384
Wu SD, Storer RH, Pei-Chann C (1993) One-machine rescheduling heuristics with efficiency and stability as criteria. Comput Oper Res 20:1–14
Tamer Unal A, Uzsoy R, Kiran AS (1997) Rescheduling on a single machine with part-type dependent setup times and deadlines. Ann Oper Res 70:93–113
Qi X, Bard JF, Yu G (2006) Disruption management for machine scheduling: the case of SPT schedules. Int J Prod Econ 103:166–184
Allahverdi A (1996) Two-machine proportionate flowshop scheduling with breakdowns to minimize maximum lateness. Comput Oper Res 23:909–916
Rahman HF, Sarker RA, Essam DL, Guijuan C (2014) A memetic algorithm for solving permutation flow shop problems with known and unknown machine breakdowns, in 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 42–49
Katragjini K, Vallada E, Ruiz R (2013) Flow shop rescheduling under different types of disruption. Int J Prod Res 51:780–797
Ruiz R, Garcia-Diaz JC, Maroto C (2007) Considering scheduling and preventive maintenance in the flowshop sequencing problem. Comput Oper Res 34:3314–3330
Perez-Gonzalez P, Framinan JM (2009) Scheduling permutation flowshops with initial availability constraint: analysis of solutions and constructive heuristics. Comput Oper Res 36:2866–2876
González PP, Torres JMF, Parente JMM, Pineda A (2009) Comparison of heuristics for rescheduling in permutation flowshops. In XIII Congreso de Ingeniería de Organización, pp. 1498–1506
Fahmy SA, Balakrishnan S, ElMekkawy TY (2009) A generic deadlock-free reactive scheduling approach. Int J Prod Res 47:5657–5676
Hasan SMK, Sarker R, Essam D (2011) Genetic algorithm for job-shop scheduling with machine unavailability and breakdowns. Int J Prod Res 49:4999–5015
Sarker R, Essam D, Hasan S, Karim A (2015) Managing risk in production scheduling under uncertain disruption, Artificial Intelligence Engineering Design, Analysis Manufacturing, pp. 1–11
Sarker R, Omar M, Hasan SMK, Essam D (2013) Hybrid evolutionary algorithm for job scheduling under machine maintenance. Appl Soft Comput 13:1440–1447
Al-Hinai N, ElMekkawy TY (2011) Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm. Int J Prod Econ 132:279–291
Hasan SK (2009) Evolutionary algorithms for solving job-shop scheduling problems in the presence of process interruptions, University of New South Wales
Wagner HM (1959) An integer linear-programming model for machine scheduling. Nav Res Logist Q 6:131–140
Ong Y-S, Lim M-H, Neri F, Ishibuchi H (2009) Special issue on emerging trends in soft computing: memetic algorithms. Soft Comput—A Fusion Foundations, Methodologies Applications 13:739–740
Akkan C (1997) Finite-capacity scheduling-based planning for revenue-based capacity management. Eur J Oper Res 100:170–179
Burke EK, Smith A (1999) A memetic algorithm to schedule planned maintenance for the national grid. Journal of Experimental Algorithmics (JEA) 4:1–13
Merz P, Freisleben B (2001) Memetic algorithms for the traveling salesman problem. Complex Syst 13:297–346
Tang J, Lim MH, Ong YS, Er MJ (2005) Solving large scale combinatorial optimization using PMA-SLS. In Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, pp. 621–628
Goldberg DE, Holland JH (1988) Genetic algorithms and machine learning. Mach Learn 3:95–99
Murata T, Ishibuchi H, Tanaka H (1996) Genetic algorithms for flowshop scheduling problems. Comput Ind Eng 30:1061–1071
Taillard E (1990) Some efficient heuristic methods for the flow-shop sequencing problem. Eur J Oper Res 47:65–74
Zhu KQ, Liu Z (2004) Empirical study of population diversity in permutation-based genetic algorithm. In Genetic and Evolutionary Computation–GECCO 2004, pp. 420–421
Hasan SK, Sarker R, Essam D, Cornforth D (2009) Memetic algorithms for solving job-shop scheduling problems. Memet Comput 1:69–83
Yuan X, Wang L, Yuan Y, Zhang Y, Cao B, Yang B (2008) A modified differential evolution approach for dynamic economic dispatch with valve-point effects. Energy Convers Manag 49:3447–3453
Acknowledgments
This research is partially supported by ARC DP170102416 awarded to R. Sarker and D. Essam.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rahman, H.F., Sarker, R. & Essam, D. Multiple-order permutation flow shop scheduling under process interruptions. Int J Adv Manuf Technol 97, 2781–2808 (2018). https://doi.org/10.1007/s00170-018-2146-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-018-2146-z