Sequencing two classes of jobs on a machine with an external no-idle constraint

Abstract

In this paper, we deal with a special type of scheduling problem. There are two classes of jobs to be processed on a single machine. Jobs of class A are directly delivered to the customers and we want to minimise their total flow time. Jobs of class B do not contribute to the objective function but must respect a no-idle constraint (i.e. they are required to keep an external downstream machine busy). This problem arises in some real-world production environments where the downstream process must not be interrupted because of technological constraints, economic viability or because the firm is bound to keep the external process continuously active (e.g. a contract with a downstream firm imposing penalties if the supply is interrupted). We prove that the general problem is NP-Hard. We introduce two mathematical programming-based approaches and some constructive heuristics. The various approaches are compared on the basis of a large computational campaign.

Keywords:

• Scheduling
• complexity analysis
• heuristics
• mixed integer linear programming

Disclosure statement

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

Data Availability Statement

The data that support the findings of this study are available from the corresponding author upon reasonable request.

Additional information

Notes on contributors

Alessandro Agnetis

Alessandro Agnetis received the Ph.D. degree in Systems Engineering from the Universitá di Roma La Sapienza in 1992, where he became Assistant Professor in Automation 1994. In 1998, he became Associate Professor of Operations Research at the Universitá di Siena, where he is Full Professor since 2001. He has lead various projects concerning resource management in production and healthcare. His main research interests concern combinatorial optimisation models for complex resource allocation problems, including planning and scheduling in manufacturing and services. He has published more than 80 papers on international scientific journals, and he currently serves as Associate Editor for IISE Transactions, Journal of Scheduling and 4OR – the journal of the Italian, French and Belgian OR Societies.

Marco Pranzo

Marco Pranzo is Associate Professor in Operations Research at University of Siena from 2019. He was Assistant Professor at University of Siena from 2006 to 2019. In 2003, he obtained the Ph.D. in Operations Research from University ‘La Sapienza’ (Rome), and in 1999 he graduated in Computer Science Engineering from Roma Tre University. He is the author of more than 50 papers on international journals or book chapters. His research interests mainly focus on scheduling problems with applications to complex systems as manufacturing, public transportation and healthcare management.