TWO PARETO OPTIMUM-BASED HEURISTIC ALGORITHMS FOR MINIMIZING TARDINESS AND LATE JOBS IN THE SINGLE MACHINE FLOWSHOP PROBLEM

MATTHEW  GRADWOHL; GUIDIO  SEWA; OKE BLESSING  OGHOJAFOR; RICHARD  WILOUWOU; MUMINU OSUMAH ADAMU; CHRISTOPHER  THRON

MATTHEW GRADWOHL DEPARTMENT OF SCIENCE AND MATHEMATICS, TEXAS A&M UNIVERSITY-CENTRAL TEXAS, KILLEEN TX USA
GUIDIO SEWA INSTITUT DE MATHE´MATIQUES ET DE SCIENCES PHYSIQUES, PORTO NOVO, BENIN REPUBLIC.
OKE BLESSING OGHOJAFOR DEPARTMENT OF STATISTICS, UNIVERSITY OF LAGOS. NIGERIA
RICHARD WILOUWOU UNIVERSITY OF SOUTH BRITTANY, LORIENT FRANCE.
MUMINU OSUMAH ADAMU DEPARTMENT OF STATISTICS, UNIVERSITY OF LAGOS. NIGERIA
CHRISTOPHER THRON DEPARTMENT OF SCIENCE AND MATHEMATICS, TEXAS A&M UNIVERSITY-CENTRAL TEXAS, KILLEEN TX USA

Keywords: flowshop, scheduling, optimization, lateness, heuristic, Pareto, neural network

Abstract

Flowshop problems play a prominent role in operations research, and have considerable practical significance. The single machine flowshop problem is of particular theoretical interest. Until now the problem of minimizing late jobs or job tardiness can only be solved exactly by computationally intensive methods such as dynamic programming or linear programming. In this paper we introduce, test, and optimize two new heuristic algorithms for mixed tardiness and late job minimization in single-machine flowshops. The two algorithms both build partial schedules iteratively. Both also retain Pareto optimal solutions at intermediate stages, to take into account both tardiness and late jobs within the partial schedule, as well as the effect of partial completion time on not-yet scheduled jobs. Both algorithms can potentially be applied to scenarios with hundreds of jobs, with execution times running from less than a second to a few minutes. Although they are slower than dispatch rule-based heuristics, the solutions obtained are far better. We also attempted a neural-network solution which performs poorly, and propose reasons why neural networks may not be a suitable approach.

References

[1] Hafewa Bargaoui, Olfa Belkahla Driss, and Khaled Gh´edira. Minimizing makespan in multi- factory flow shop problem using a chemical reaction metaheuristic. In 2016 IEEE Congress on Evolutionary Computation (CEC), pages 2919–2926. IEEE, 2016.
[2] Amar Oukil and Ahmed El-Bouri. Ranking dispatching rules in multi-objective dynamic flow shop scheduling: a multi-faceted perspective. International Journal of Production Research, 59(2):388–411, 2021.
[3] Harwin Kurniawan, Tanika D Sofianti, Aditya Tirta Pratama, and Prianggada Indra Tanaya. Optimizing production scheduling using genetic algorithm in textile factory. Journal of System and Management Sciences, 4(4):27–44, 2014.
[4] MK Marichelvam and M Geetha. Solving tri-objective multistage hybrid flow shop scheduling problems using a discrete firefly algorithm. International Journal of Intelligent Engineering Informatics, 2(4):284–303, 2014.
[5] TS Benthem. Solving a multi-objective hybrid flow shop scheduling problem with practical constraints from the food industry. Master’s thesis, University of Twente, 2021.
[6] Shuai Chen, Quan-Ke Pan, Liang Gao, and Hong-yan Sang. A population-based iterated greedy algorithm to minimize total flowtime for the distributed blocking flowshop scheduling problem. Engineering Applications of Artificial Intelligence, 104:104375, 2021.
[7] Heiner Ackermann, Sandy Heydrich, and Christian Weiß. Analyzing and optimizing the throughput of a pharmaceutical production process. In Operations Research Proceedings 2019, pages 591–597. Springer, 2020.
[8] Tanzila Azad and Asif Ahmed Sarja. A comparative analysis of heuristic metaheuristic and exact approach to minimize make span of permutation flow shop scheduling. American Journal of Industrial Engineering, 8(1):1–8, 2021.
[9] Eva Vallada, Rub´en Ruiz, and Gerardo Minella. Minimising total tardiness in the m- machine flowshop problem: A review and evaluation of heuristics and metaheuristics. Computers & Operations Research, 35(4):1350–1373, 2008.
[10] Eric Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285, 1993.
[11] Eva Vallada, Rub´en Ruiz, and Jose M Framinan. New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research, 240(3):666–677, 2015.
[12] Michael Pinedo and Khosrow Hadavi. Scheduling: Theory, algorithms and systems devel- opment. In Wolfgang Gaul, Achim Bachem, Wilhelm Habenicht, Wolfgang Runge, and Werner W. Stahl, editors, Operations Research Proceedings 1991, volume 1991, pages 35–
42. Springer, Berlin, Heidelberg, 1992.
[13] Steven Nahmias and Tava Olsen. Production and Operations Analysis, chapter 9, page 490. Waveland Press, 7th edition, 2015.
[14] Cecilia E Nugraheni, Luciana Abednego, and Maria Widyarini. A combination of palmer algorithm and gupta algorithm for scheduling problem in apparel industry. International Journal of Fuzzy Logic Systems, 11(1):1–12, 2021.
[15] Christophe Sauvey and Nathalie Sauer. Two neh heuristic improvements for flowshop scheduling problem with makespan criterion. Algorithms, 13(5):112, 2020.
[16] Yeong-Dae Kim. Heuristics for flowshop scheduling problems minimizing mean tardiness.
Journal of the Operational Research Society, 44(1):19–28, 1993.
[17] Victor Fernandez-Viagas and Jose M Framinan. NEH-based heuristics for the permuta- tion flowshop scheduling problem to minimise total tardiness. Computers & Operations Research, 60:27–36, 2015.