Mathematical formulations for the parallel machine scheduling problem with a single server

Abstract

This paper addresses the problem of scheduling independent jobs on identical parallel machines with a single server to minimise the makespan. We propose mixed integer programming (MIP) formulations to solve this problem. Each formulation reflects a specific concept on how the decision variables are defined. Moreover, we present inequalities that can be used to improve those formulations. A computational study is performed on benchmark instances from the literature to compare the proposed MIP formulations with other known formulations from the literature. It turns out that our proposed time-indexed variables formulation outperforms by far the other formulations. In addition, we propose a very efficient MIP formulation to solve a particular case of the problem with a regular job set. This formulation is able to solve all regular instances for the case of 500 jobs and 5 machines in less than 5.27 min, where all other formulations are not able to produce a feasible solution within 1 h.

Keywords:

• Identical parallel machine scheduling
• scheduling with a single server
• mixed integer programming

Acknowledgments

The authors wish to thank the anonymous referees for their careful reading and helpful suggestions that have contributed significantly towards improving the article.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Notes on contributors

Abdelhak Elidrissi

Abdelhak Elidrissi received the Engineer degree from the Department of Industrial Engineering, National Higher School of Electricity and Mechanics, Casablanca, Morocco, and, the Master of Science degree from the Department of Industrial Engineering, National School of Engineers of Metz, France, both in 2015. Since September 2017, Abdelhak ELIDRISSI is a PhD student in operations research and computer science jointly in Mohammadia School of Engineers, Rabat, Morocco, and, Polytechnic University of Haut-de-France, Valenciennes, France. His main research interest is scheduling optimisation.

Rachid Benmansour

Rachid Benmansour graduated as an Engineer from the Mohammadia School of Engineers in 2003 (Morocco). In 2011, he received a PhD in computer science from Pierre and Marie Curie University, Paris 6 (France). From 2013 to 2017, he worked as associate professor in the University of Valenciennes where he participated in numerous national and European research projects. In 2017, he joined the National Institute of Statistics and Applied Economics (INSEA) in Morocco as associate professor.Dr. Benmansour has been a visiting professor in Germany, Morocco and Tunisia. He has also spent scientific stays in the United States (North Carolina State University) and Tunisia (Sfax National School of Engineering). His main research interests include combinatorial optimisation, supply chain management, maintenance and scheduling.

Mohammed Benbrahim

Mohammed Benbrahim obtained the postgraduate doctoral degree in operations research at the Faculty of Sciences of Rabat in 1985. Then the title of doctor of science from the Free University of Brussels in 1999. He has worked at the Mohammadia School of Engineers of Rabat since October 1979. From October 1979 until November 1985 as assistant teacher, then from November 1985 until January 1999 as assistant professor and from January 1999 as professor. Deputy Head of the Industrial Engineering Department from January 2003 to November 2005, then Head of the Industrial Engineering Department from November 2005 to November 2007. Member of the Moroccan Society for Operational Research. Member of the MOAD6 research team, of the MASI laboratory and of the E3S (Engineering for Smart & Sustainable Systems) research center. Works on workshop scheduling issues and especially on scheduling issues on identical parallel machines.

David Duvivier

Since September 2017, Dr. David Duvivier is a Full Professor of Computer Science at the Universitè Polytechnique Hauts-de-France (UPHF), in the Laboratory of Industrial and Human Automation control, Mechanical Engineering and Computer Science (LAMIH UMR CNRS 8201). Since January 2020, Dr. David DUVIVIER is Deputy Director at LAMIH UMR CNRS 8201. From January 2012 to August 2017, Dr. David Duvivier was an Associate Professor of Computer Science at the University of Valenciennes and Hainaut-Cambrésis (UVHC, now UPHF), in the LAMIH, UMR CNRS 8201. From 2005 to 2011, Dr. David DUVIVIER was an Associate Professor at the Université du Littoral-Côte d'Opale (ULCO, Calais, France), in the Laboratoire d'Informatique Signal et Image de la Cote d'Opale (LISIC). From 2000 to 2005, he was a researcher at the Centre de Recherches et d'Etudes en Gestion Industrielle of the Catholic University of Mons (CREGI-FUCaM, now UCL-Mons, Belgium). He received the Master's degree in Computer Science from the Université des Sciences et Technologies de Lille (USTL, France), in 1994. He obtained a PhD degree in Computer Science at the Université du Littoral-Côte d'Opale in the LIL Laboratory (now LISIC), in 2000. He has been involved in several R&D projects in Belgium and in France with applications to Intelligent Transportation Systems (ITS); planning and scheduling of industrial and healthcare problems; avionics; optimisation of preventive maintenance… His main research interests are operational research, discrete optimisation, simulation, modelling, multicriteria limited time decision making, hybridisation (optimisation & simulation), metaheuristics, planning and scheduling.