Novel efficient formulation and matheuristic for large-sized unrelated parallel machine scheduling with release dates

Abstract

This study investigates the unrelated parallel machine scheduling problem with release dates to minimise the makespan. The solution to this problem finds wide applications in manufacturing and logistics systems. Due to the strong NP-hardness of the problem, most researchers develop heuristics, and the largest instances they consider are limited to 400 jobs. To tackle this problem, we develop a novel mixed-integer linear program (MILP) with significantly fewer integer variables than the state-of-the-art ones. The proposed MILP does not rely on a binary sequence variable usually used in the existing models. To deal with large-sized instances, a new three-stage matheuristic algorithm (TSMA) is proposed to obtain scheduling decisions. It uses a dispatching rule to sequentially schedule jobs on machines. Then a reassignment procedure is performed to reduce the makespan. Finally, it employs a re-optimisation procedure based on the proposed MILP to perform job moves and exchanges between two selected machines. We conduct numerical experiments on 1440 instances with up to 3000 jobs and 20 machines. Our results first clearly indicate that the proposed model significantly outperforms existing ones. Moreover, the results on large-sized instances show that the proposed TSMA can obtain high-quality near-optimal solutions in a short computation time.

Keywords:

• Parallel machine scheduling
• release date
• makespan
• mixed-integer linear programming
• multi-stage matheuristic
• large-scale combinatorial optimization

Acknowledgments

We thank an associate editor and two anonymous referees for their valuable suggestions on an earlier version of this paper.

Data availability statement

The data that support the findings of this study are openly available at https://www.dmu-yantongli.com/instances.

Disclosure statement

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

Additional information

Funding

This work was partly supported by grants 71901069 and 71871159 from the National Natural Science Foundation of China, grant 21YJA630096 from the Humanities and Social Science Foundation of the Chinese Ministry of Education, grants 2015-04893 and 2019-00094 from the Canadian Natural Sciences and Engineering Research Council, and by the 2nd Fujian ‘Young Eagle Program’ Youth Top Talent Program.

Notes on contributors

Yantong Li

Yantong Li received the B.S. degree in traffic and transportation from Beijing Jiaotong University, Beijing, China, in 2011, the M.S. degree in transportation planning and management from Military Transportation University, Tianjin, China, in 2013, and the Ph.D. degree in Automation from University of Paris Saclay, Evry, France, in 2019. Dr. Li is currently an Associate Professor with Dalian Maritime University, Dalian, China. His research interests include scheduling theory and applications, integrated optimisation models and algorithms, and mathematical programming-based methods.

Jean-François Côté

Jean-François Côté is an associate professor at the Department of Operations and Decision Systems of Université Laval, Canada. He holds a B.Sc., a M.Sc. and a Ph.D. degree in computer science from the Université of Montréal, Canada. His research interests are in the development of exact and heuristic algorithms for routing, cutting, and packing problems, and industrial applications.

Leandro C. Coelho

Leandro C. Coelho received the B.Sc. degree in electrical and industrial engineering and an M.Sc. degree in industrial engineering (transportation and logistics) from the Federal University of Santa Catarina (UFSC), Brazil, in 2005 and 2008 respectively, and the Ph.D. degree from HEC Montréal, Canada, in 2012. He is a full professor at Université Laval, Canada, where he holds the Canada research chair in integrated logistics. His research interests lie in the development of optimisation algorithms for transportation problems.

Peng Wu

Peng Wu received the B.S. degree and an M.S. degree in management science and engineering from Northwestern Polytechnical University, Xi'an, China, in 2010 and 2013, respectively; and the Ph.D. degree in mathematics and computer science from University of Paris-Saclay, France in 2016. He is a professor at School of Economics and Management, Fuzhou University. His research interest is the optimisation of complex transportation, logistics, and production systems based on operations research. He is authored or co-authored nearly 40 journal papers in the above areas including INFORMS Journal on Computing, IEEE Transactions, Decision Support Systems, International Journal of Production Research, Transportation Research Part B, Annals of Operations Research, etc.