Sequencing two classes of jobs on a machine with an external no-idle constraint. Issue 7 (3rd April 2023)

• Record Type: Journal Article
• Authors: Agnetis, Alessandro; Pranzo, Marco
• Is Part Of: International journal of production research. Volume 61:Issue 7(2023)
• Page Start: 2178
• Page End: 2189
• Publication Date: 2023-04-03
• Subjects: Scheduling -- complexity analysis -- heuristics -- mixed integer linear programming; Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2022.2065551
• Languages: English
• ISSNs: 0020-7543

Abstract

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.