More effective heuristics for a two-machine no-wait flowshop to minimize maximum lateness

Abstract: We address a manufacturing environment with the no-wait constraint which is common in industries such as metal, plastic, and semiconductor. Setup times are modelled as uncertain with the objective of minimizing maximum lateness which is an important performance measure for customer satisfaction. This problem has been addressed in scheduling literature for the two-machine no-wait flowshop where dominance relations were presented. Recently, another dominance relation was presented and shown to be about 90% more efficient than the earlier ones. In the current paper, we propose two new dominance relations, which are less restrictive than the earlier ones in the literature. The new dominance relations are shown to be 140% more efficient than the most recent one in the literature. As the level of uncertainty increases, the newly proposed dominance relation performs better, which is another strength of the newly proposed dominance relation. Moreover, we also propose constructive heuristics and show that the best of the newly proposed heuristics is 95% more efficient than the existing one in the literature under the same CPU time.

How to cite this paper

 Aydilek, H., Aydilek, A., Allahverdi, M & Allahverdi, A. (2022). More effective heuristics for a two-machine no-wait flowshop to minimize maximum lateness.International Journal of Industrial Engineering Computations , 13(4), 543-556.

Refrences

Akande, S., Oluleye, A., & Oyetunji, E. (2018). Effective heuristics for solving dynamic variant of single processor total tardiness problems. Journal of Project Management, 3(1), 13-22.
Allahverdi, A., & Allahverdi, M. (2018). Two-machine no-wait flowshop scheduling problem with uncertain setup times to minimize maximum lateness. Computational and Applied Mathematics, 37(5), 6774-6794.
Allahverdi, M., Aydilek, H., Aydilek, A., & Allahverdi, A. (2021). A better dominance relation and heuristics for two-machine no-wait flowshops with maximum lateness performance measure. Journal of Industrial & Management Optimization, 17(4), 1973.
Allahverdi, A. (2005). Two-machine flowshop scheduling problem to minimize makespan with bounded setup and processing times. Int. Journal of Agile Manufacturing, 8, 145-153.
Allahverdi, A. (2015). The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, 246(2), 345-378.
Allahverdi, A. (2016). A survey of scheduling problems with no-wait in process. European Journal of Operational Research, 255(3), 665-686.
Allahverdi, A. (2022a). A survey of scheduling problems with uncertain interval/bounded processing/setup times. Journal of Project Management, 7(4), 255-264.
Allahverdi, M. (2022b). An improved algorithm to minimize the total completion time in a two-machine no-wait flowshop with uncertain setup times. Journal of Project Management, 7(1), 1-12.
Allahverdi, A., Aldowaisan, T., & Sotskov, Y.N. (2003). Two-machine flowshop scheduling problem to minimize makespan or total completion time with random and bounded setup times. Int. Journal of Mathematics and Mathematical Sciences, 39, 2475-2486.
Aydilek, A., Aydilek, H., & Allahverdi, A. (2013). Increasing the profitability and competitiveness in a production environment with random and bounded setup times. International Journal of Production Research, 51(1), 106-117.
Aydilek, A., Aydilek, H., & Allahverdi, A. (2015). Production in a two-machine flowshop scheduling environment with uncertain processing and setup times to minimize makespan. International Journal of Production Research, 53(9), 2803-2819.
Aydilek, A., Aydilek, H., & Allahverdi, A. (2017). Algorithms for minimizing the number of tardy jobs for reducing production cost with uncertain processing times. Applied Mathematical Modelling, 45, 982-996.
Braga-Santos, S., Barroso, G., & Prata, B. (2022). A size-reduction algorithm for the order scheduling problem with total tardiness minimization. Journal of Project Management, 7(3), 167-176.
Braun, O., Lai, T. C., Schmidt, G., & Sotskov, Y. N. (2002). Stability of Johnson's schedule with respect to limited machine availability. International Journal of Production Research, 40(17), 4381-4400.
Dileepan, P. (2004). A note on minimizing maximum lateness in a two-machine no-wait flowshop. Computers & Operations Research, 31(12), 2111-2115.
Gonzalez-Neira, E. M., Ferone, D., Hatami, S., & Juan, A. A. (2017). A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times. Simulation Modelling Practice and Theory, 79, 23-36.
González-Neira, E., & Montoya-Torres, J. (2019). A simheuristic for bi-objective stochastic permutation flow shop scheduling problem. Journal of Project Management, 4(2), 57-80.
Guevara-Guevara, A., Gómez-Fuentes, V., Posos-Rodríguez, L., Remolina-Gómez, N., & González-Neira, E. (2022). Earliness/tardiness minimization in a no-wait flow shop with sequence-dependent setup times. Journal of Project Management, 7(3), 177-190.
Hall, N. G., & Posner, M. E. (2001). Generating experimental data for computational testing with machine scheduling applications. Operations Research, 49(6), 854-865.
Hall, N. G., & Sriskandarajah, C. (1996). A survey of machine scheduling problems with blocking and no-wait in process. Operations research, 44(3), 510-525.
Hecker, F. T., Stanke, M., Becker, T., & Hitzmann, B. (2014). Application of a modified GA, ACO and a random search procedure to solve the production scheduling of a case study bakery. Expert systems with applications, 41(13), 5882-5891.
Hsu, V. N., De Matta, R., & Lee, C. Y. (2003). Scheduling patients in an ambulatory surgical center. Naval Research Logistics (NRL), 50(3), 218-238.
Keshavarz, T., & Salmasi, N. (2013). Makespan minimisation in flexible flowshop sequence-dependent group scheduling problem. International Journal of Production Research, 51(20), 6182-6193.
Kim, Y. D. (1993). A new branch and bound algorithm for minimizing mean tardiness in two-machine flowshops. Computers & Operations Research, 20(4), 391-401.
Kim, S. C., & Bobrowski, P. M. (1997). Scheduling jobs with uncertain setup times and sequence dependency. Omega, 25(4), 437-447.
Kim, J., Kröller, A., & Mitchell, J. (2009). Scheduling aircraft to reduce controller workload. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
Kouvelis, P., & Yu, G., (1997). Robust discrete optimization and its applications. Kluwer Academic Publishers, Boston.
Liu, S. Q., & Kozan, E. (2011). Scheduling trains with priorities: a no-wait blocking parallel-machine job-shop scheduling model. Transportation Science, 45(2), 175-198.
Macchiaroli, R., Mole, S., & Riemma, S. (1999). Modelling and optimization of industrial manufacturing processes subject to no-wait constraints. International Journal of Production Research, 37(11), 2585-2607.
Matsveichuk, N. M., Sotskov, Y. N., & Werner, F. (2011). The dominance digraph as a solution to the two-machine flow-shop problem with interval processing times. Optimization, 60(12), 1493-1517.
Rossit, D.A., Toncovich, A., Rossit, D.G., & Nesmachnow, S. (2021). Solving a flow shop scheduling problem with missing operations in an Industry 4.0 production environment. Journal of Project Management, 6, 33-44.
Seidgar, H., Kiani, M., Abedi, M., & Fazlollahtabar, H. (2014). An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flow shop problem. International Journal of Production Research, 52(4), 1240-1256.
Sotskov, Y. N. (2012). Measure of uncertainty for Bellman-Johnson problem with interval data/Yu. N. Sotskov, NM Matsveichuk. Cybernetics and System Analysis, 48(5), 641-652.
Sotskov, Y. N., Egorova, N. G., & Lai, T. C. (2009). Minimizing total weighted flow time of a set of jobs with interval processing times. Mathematical and Computer Modelling, 50(3-4), 556-573.
Sotskov, Y. N., & Lai, T. C. (2012). Minimizing total weighted flow time under uncertainty using dominance and a stability box. Computers & Operations Research, 39(6), 1271-1289.
Vallada, E., & Ruiz, R. (2010). Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. Omega, 38(1-2), 57-67.
Wang, K., & Choi, S. H. (2012). A decomposition-based approach to flexible flow shop scheduling under machine breakdown. International Journal of Production Research, 50(1), 215-234.