Abstract
In static-deterministic flow shop scheduling, solution algorithms are often tested by problem instances with uniformly distributed processing times. However, there are scheduling problems where a certain structure, variability or distribution of processing times appear. While the influence of these aspects on common objectives, like makespan and total completion time, has been discussed intensively, the efficiency-oriented objectives core idle time and core waiting time have not been taken into account so far. Therefore, a first computational study using complete enumeration is provided to analyze the influence of different structures of processing times on core idle time and core waiting time. The results show that in some cases an increased variability of processing times can lead to easier solvable problems.
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
Benkel, K., Jørnsten, K., Leisten, R.: Variability aspects in flowshop scheduling systems. In: International Conference on Industrial Engineering and Systems Management (IESM) (2015), pp. 118–127
De Matta, R.: Minimizing the total waiting time of intermediate products in a manufacturing process. Int. Trans. Oper. Res. 26(3), 1096–1117 (2019)
Fernandez-Viagas, V., Framinan, J.M.: Reduction of permutation flowshop problems to single machine problems using machine dominance relations. Comput. Oper. Res. 77, 96–110 (2017)
Framinan, J.M., Perez-Gonzalez, P.: On heuristic solutions for the stochastic flowshop scheduling problem. Eur. J. Oper. Res. 246(2), 413–420 (2015)
Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discret. Math. 5, 287–326 (1979)
Juan, A.A., Barrios, B.B., Vallada, E., Riera, D., Jorba, J.: A simheuristic algorithm for solving the permutation flow shop problem with stochastic processing times. Simul. Model. Pract. Theory 46, 101–117 (2014)
Liu, W., Jin, Y., Price, M.: A new heuristic to minimize system idle time for flowshop scheduling. In: Poster presented at the 3rd Annual EPSRC Manufacturing the Future Conference, Glassgow (2014)
Monma, C.L., Kan, A.R.: A concise survey of efficiently solvable special cases of the permutation flow-shop problem. RAIRO Oper. Res. 17(2), 105–119 (1983)
Pinedo, M.L.: Scheduling: Theory, Algorithms, and Systems. Springer (2016)
Reeves, C.R.: A genetic algorithm for flowshop sequencing. Comput. Oper. Res. 22(1), 5–13 (1995)
Rinnooy Kan, A.H.G.: Machine Scheduling Problems: Classification, Complexity and Computation. Martinus Nijhoff, The Hague (1976)
Schollenberger, H.: Analyse und Verbesserung der Arbeitsabläufe in Betrieben der Reparaturlackierung, Univ.-Verlag Karlsruhe (2006)
Taillard, E.: Benchmarks for basic scheduling problems. Eur. J. Oper. Res. 64(2), 278–285 (1993)
Vallada, E., Ruiz, R., Framinan, J.M.: New hard benchmark for flowshop scheduling problems minimising makespan. Eur. J. Oper. Res. 240(3), 666–677 (2015)
Watson, J.P., Barbulescu, L., Whitley, L.D., Howe, A.E.:. Contrasting structured and random permutation flow-shop scheduling problems: search-space topology and algorithm performance. INFORMS J. Comput. 14(2), 98–123 (2002)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Maassen, K., Perez-Gonzalez, P. (2020). Diversity of Processing Times in Permutation Flow Shop Scheduling Problems. In: Neufeld, J.S., Buscher, U., Lasch, R., Möst, D., Schönberger, J. (eds) Operations Research Proceedings 2019. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-030-48439-2_67
Download citation
DOI: https://doi.org/10.1007/978-3-030-48439-2_67
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-48438-5
Online ISBN: 978-3-030-48439-2
eBook Packages: Business and ManagementBusiness and Management (R0)