A GRASP for a real-world scheduling problem with unrelated parallel print machines and sequence-dependent setup times

Abstract

We consider a real-world scheduling problem arising in the colour printing industry. The problem consists in assigning print jobs to a heterogeneous set of flexographic printer machines and finding a processing sequence for the jobs assigned to each machine. The machines are characterised by a limited sequence of colour groups and can equip additional components (e.g. embossing rollers and perforating rolls) to process jobs that require specific treatments. The process to equip a machine with an additional component or to clean a colour group takes a long time, with the effect of significantly raising the setup times. The aim is to minimise a weighted sum of total weighted tardiness and total setup time. The problem derives from the activities of an Italian food packaging company. To solve it, we developed a greedy randomised adaptive search procedure equipped with several local search procedures. The excellent performance of the algorithm is proved by extensive computational experiments on real-world instances, for which it produced good-quality solutions within a limited computing time. The algorithm is currently in use at the company to support their weekly scheduling decisions.

Keywords:

• Metaheuristics
• food industry
• real-world scheduling
• sequence-dependent setup times

Acknowledgements

We acknowledge financial support from Istituto Stampa s.r.l. (Italy). The work originates from the daily activity of Istituto Stampa s.r.l., a company whose headquarters is located in Reggio Emilia (Italy). The company operates in the field of packaging industry by producing and printing packaging materials for food products since 1933. We are grateful to the three anonymous reviewers for their insightful and helpful comments.

Data availability statement

The data that support the findings of this study are openly available in Instances at https://github.com/regor-unimore/Parallel-Print-Machine-Problem-with-Setup-Times.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Manuel Iori

Manuel Iori is professor of Operations Research at the University of Modena and Reggio Emilia. His research lies in the fields of combinatorial optimisation and logistics, with a focus on exact and heuristic algorithms for travelling salesman, vehicle routing, bin packing, production and scheduling problems. He has published more than 90 papers in international journals, including Operations Research and Mathematical Programming. He is member of the research centres CIRRELT, INdAM, AIRI and INTERMECH MORE. He collaborates with several companies and international Universities for the solutions of real-world optimisation problems, by designing and developing solution methods and decision support systems.

Alberto Locatelli

Alberto Locatelli is a Ph.D. student from the University of Modena and Reggio Emilia at the Department of Sciences and Methods for Engineering. He graduated in Mathematics at University of Padua developing a particular interest in Combinatorial Optimisation. Then, he got a research grant and joined the Operational Research academic group in the University of Trieste. Currently, his main research areas cover knapsack problems, tool switching problems, and scheduling optimisation techniques for problems arising from industrial companies.

Marco Locatelli

Marco Locatelli is Full Professor of Operations Research at the University of Parma. His main research interests are the theoretical, practical and applicative aspects of optimisation. He has published about one hundred papers in international journals and co-authored, with F. Schoen, the book Global Optimization: Theory, Algorithms, and Applications for the Society for Industrial and Applied Mathematics (SIAM). He has been nominated EUROPT Fellow in 2018. He is currently in the editorial board of the journals Computational Optimization and Applications, Journal of Global Optimization, and Operations Research Forum.