Constraint programming approach for multi-resource-constrained unrelated parallel machine scheduling problem with sequence-dependent setup times

Abstract

This paper studies the multi-resource-constrained unrelated parallel machine scheduling problem under various operational constraints with the objective of minimising maximum completion time among the scheduled jobs. Sequence-dependent setup times, precedence relations, machine eligibility restrictions and release dates are incorporated into the problem as operational constraints to reflect real-world manufacturing environments. The considered problem is in NP-hard class of problems, which cannot be solved in deterministic polynomial time. Our aim in this study is to develop an exact solution approach based on constraint programming (CP), which shows good performance in solving scheduling problems. In this regard, we propose a CP model and enrich this model by adding lower bound restrictions and redundant constraints. Moreover, to achieve a reduction in computation time, we propose two branching strategies for the proposed CP model. The performance of the CP model is tested using randomly generated and benchmark instances from the literature. The computational results indicate that the proposed CP model outperforms the best solutions with an average gap of 15.52%.

KEYWORDS:

• Unrelated parallel machines
• scheduling
• multiple resources
• constraint programming
• branching strategies

Acknowledgements

We would like to thank Sedef Cali for the support in the model development.

Disclosure statement

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

Additional information

Notes on contributors

Pinar Yunusoglu

Pinar Yunusoglu is a research assistant at Izmir Bakircay University, Department of Industrial Engineering. Her field of interest mainly focuses on operations research applications in manufacturing and service systems. She has research interests including combinatorial optimisation problems, scheduling, constraint programming, and heuristics. During her MSc, her research centred on constraint programming-based solution approaches for solving highly constrained scheduling problems.

Seyda Topaloglu Yildiz

Seyda Topaloglu Yildiz is Professor of Industrial Engineering at Dokuz Eylul University (DEU), Turkey. She received her Master and Ph.D. degrees in Industrial Engineering from DEU. Her research interests are: mathematical modelling, scheduling, constraint programming, and assembly line balancing.