Scheduling unrelated machines with job splitting, setup resources and sequence dependency

ABSTRACT

We examine the parallel machine scheduling problem where a set of jobs are to be processed by a set of unrelated parallel machines. We examine the most general among the variations for which an exact method has been proposed regarding makespan minimisation. This is because, apart from unrelated machines, we allow for (i) job splitting: each job's quantity can be split and processed by multiple machines simultaneously; (ii) sequence- and machine-dependent setup times: the setup time when job j succeeds k is different than the time when k succeeds j and varies also per machine m; and (iii) setup resource constraints: the number of setups that can be performed simultaneously on different machines is restricted. We present novel lower bound formulations and a heuristic that solves instances of up to 1000 jobs in a few minutes at an average gap of less than $20\mathrm{\%}$. Then, we propose a logic-based Benders decomposition, which, coupled with our heuristic, solves instances of up to 200 jobs and 20 machines to near optimality in less than two hours. Our method is used for a broad range of instances from textile manufacturing, thus yielding valuable managerial insights on makespan's versatility under varying machines or resources.

KEYWORDS:

• Parallel machine scheduling
• sequence-dependent setup times
• job splitting
• benders decomposition
• heuristics
• textile manufacturing

Disclosure statement

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Data availability statement

Instances, results and codes that support the findings of this work are available at https://github.com/svatikiot/IJPR-submission.

Additional information

Funding

This work was supported by FACTLOG Horizon 2020 [ grant number 869951].

Notes on contributors

Ioannis Avgerinos

Ioannis Avgerinos is a Ph.D. candidate in Combinatorial Optimization at the Department of Management Science and Technology, Athens University of Economics and Business, Greece. He received the bachelor's degree in Geomatics Engineering from National Technical University of Athens, and the master's degree in Management Science and Technology from Athens University of Economics and Business. His research interests include combinatorial optimisation, decomposition methods and their implementation on transport and production scheduling problems.

Ioannis Mourtos

Ioannis Mourtos is a Professor at the Department of Management Science & Technology, Athens University of Economics and Business. He studied Computer Engineering and Informatics at University of Patras and Operations Research at London School of Economics and Political Science. His academic interests lie within Combinatorial Optimisation, Polyhedral Combinatorics and the integration of Integer Programming with Constraint Programming. His work has been applied to optimisation problems in manufacturing and logistics and has been supported by several EU-funded projects.

Stavros Vatikiotis

Stavros Vatikiotis is a Ph.D. Candidate at the Department of Management Science & Technology, Athens University of Economics and Business. He studied Electrical & Computer Engineering at National Technical University of Athens and holds a master's degree in Mathematical Modeling from the School of Applied Mathematical and Physics Sciences, National Technical University of Athens. His research interests lie in the design of combinatorial optimisation methods and their applications on industrial production environments.

Georgios Zois

Georgios Zois is a Research Associate at the Department of Management Science and Technology, Athens University of Economics and Business. He studied Computer Science at University of Ioannina, Logic, Algorithms and Computation at University of Athens and received his Ph.D. from University Pierre and Marie Curie (UPMC) on algorithmic problems for energy and temperature-efficient computing. His research interests lie in the design and analysis of efficient exact and near-optimal optimisation algorithms for real life applications in the areas of logistics and manufacturing, including location optimisation and multimodal transportation problems, as well as resource-aware production scheduling and planning.