Abstract
No-wait flow shop scheduling problem with dual criteria of makespan and system utilization time has been addressed in this paper. The objective is to schedule the n jobs on available system of machines in such a way that the weighted sum of makespan and system utilization time is the minimum possible. System utilization time is rarely found criteria of flow shop scheduling literature. Many heuristics and metaheuristics are available in the literature for flow shop scheduling problem with the criteria of makespan, and however, no heuristic is present for criteria of system utilization time. In this paper, the dominance relation has been developed for the system of two machines. Further, since the problem taken in hand is NP-hard, therefore, advanced iterated greedy algorithm (AIGA) has been developed to solve it. Design of the experiment approach has been used to estimate the parameters of AIGA. The computational experiment is carried out on some well-known scheduling benchmarks, and the results depict the superiority of the proposed algorithm over some existing techniques in the literature.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
A. Allahverdi, A survey of scheduling problems with no-wait in process. Eur. J. Oper. Res. 255(3), 665–686 (2016)
A. Allahverdi, T. Aldowaisan, No-wait flowshops with bicriteria of makespan and maximum lateness. Eur. J. Oper. Res. 152, 132–147 (2004)
A. Allahverdi, H. Aydilek, A. Aydilek, No-wait flowshop scheduling problem with two criteria; total tardiness and makespan. Eur. J. Oper. Res. 269(2), 590–601 (2017)
J.Y. Ding, S. Song, J.N.D. Gupta, R. Zhang, R. Chiong, C. Wu, An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem. Appl. Soft Comput. 30, 604–613 (2015a)
J.M. Framinan, M.S. Nagano, Evaluating the performance for makespan minimization in no-wait flowshop sequencing. J. Mater. Process. Technol. 97, 1–9 (2008)
M.R. Garey, J.R. Johnson, R. Sethi, The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1(2), 117–129 (1970)
D. Gupta, S. Bala, P. Singla, A heuristic for two machine open shop specially structured scheduling problem to minimize the rental cost, including job block criteria. Int. J. Pure Appl. Math. 86(5), 767–778 (2013)
D. Gupta, S. Sharma, P. Singla, S. Bala, Minimizing rental cost for n-jobs, 2-machines flow shop scheduling, processing time associated with probabilities including transportation time and job block criteria. Inf. Knowl. Manag. 1(3), 17–27 (2011)
J. Grabowski, J. Pempera, Some local search algorithms for no-wait flow-shop problem with makespan criterion. Comput. Oper. Res. 32, 2197–2212 (2005)
S.W. Lin, K.C. Ying, Minimizing makespan for solving the distributed no-wait flow shop scheduling problem. Comput. Ind. Eng. 99, 202–209 (2016)
M. Nawaz Jr., E.E., I. Ham, A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. Omega 11, 91–95 (1984)
H. Oztop, M.F. Tasgetiren, D.T. Eliiyi, Q.-K. Pan, Iterated greedy algorithms for the hybrid flowshop scheduling with total flow time minimization. Comput. Oper. Res. 3, 379–385 (2018)
Q.K. Pan, L. Wang, B. Qian, A novel multi-objective particle swarm optimization algorithm for no-wait flow shop scheduling problems. J. Eng. Manuf. 222, 519–539 (2008)
B. Qian, L. Wang, D.X. Huang, H.X. Wang, Multi-objective no-wait flow-shop scheduling with a memetic algorithm based on differential evolution. Soft Comput. 36(1), 209–233 (2009)
C. Rajendran, A no-wait flowshop scheduling heuristic to minimize makespan. J. Oper. Res. Soc. 45(4), 475–478 (1994)
I. Ribas, R. Companys, X.T. Martorell, An iterated greedy algorithm for flowshop scheduling problem with blocking. Omega 39, 293–301 (2011)
H. Rock, Three machine no-wait flow shop is Np-complete. J. Assoc. Comput. Mach. 31(2), 336–345 (1984)
R. Ruiz, A. Allahverdi, New heuristics for no-wait flow shops with a linear combination of makespan and maximum lateness. Int. J. Product. Res. 47, 5717–5738 (2009)
R. Ruiz, T. Stutzle, A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur. J. Oper. Res. 177(3), 2033–2049 (2007)
H. Samarghandi, T.Y. Elmekkawy, A meta-heuristic approach for solving the no-wait flow-shop problem. Int. J. Product. Res. 50, 7313–7326 (2012)
S. Sharma, D. Gupta, Minimizing rental cost under specified rental policy in two stage flow shop, the processing time associated with probabilities including break-down interval and job block criteria. Eur. J. Bus. Manag. 1(3), 60–71 (2011)
M.F. Tasgetiren, D. Kizilay, Q.-K. Pan, P.N. Suganthan, Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion. Comput. Oper. Res. 77, 111–126 (2017)
L.Y. Tseng, Y.T. Lin, A hybrid genetic algorithm for no-wait flowshop scheduling problem. Int. J. Product. Econ. 128, 144–152 (2010)
Acknowledgements
One of authors (Meenakshi Sharma) acknowledges the financial support provided by council of scientific and industrial research, New Delhi, India, in the form of SRF through grant number 09/135(0766)/2017-EMR-I.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Sharma, M., Sharma, M., Sharma, S. (2020). Advanced Metaheuristics for Bicriteria No-Wait Flow Shop Scheduling Problem. In: Nagar, A., Deep, K., Bansal, J., Das, K. (eds) Soft Computing for Problem Solving 2019 . Advances in Intelligent Systems and Computing, vol 1138. Springer, Singapore. https://doi.org/10.1007/978-981-15-3290-0_10
Download citation
DOI: https://doi.org/10.1007/978-981-15-3290-0_10
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-15-3289-4
Online ISBN: 978-981-15-3290-0
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)