Unrelated parallel machine scheduling with new criteria: Complexity and models. (August 2021)

• Record Type: Journal Article
• Authors: Bitar, Abdoul; Dauzère-Pérès, Stéphane; Yugma, Claude
• Is Part Of: Computers & operations research. Volume 132(2021)
• Publication Date: 2021-08
• Subjects: Scheduling -- Unrelated parallel machines -- Sequence-dependent setup times -- Auxiliary resources -- Complexity -- Integer linear programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105291
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A complex scheduling problem on unrelated parallel machines is studied. Auxiliary resources and sequence-dependent and machine-dependent setup times are considered. The complexity of three industrially relevant criteria are analyzed. Integer Linear Programming models are proposed. Computational experiments with the models on randomly generated instances are discussed. Abstract: In this paper, a scheduling problem on non-identical parallel machines with auxiliary resources and sequence-dependent and machine-dependent setup times is studied. This problem can be found in various manufacturing contexts, and in particular in workshops of wafer manufacturing facilities. Three different criteria are defined and analyzed: The number of products completed before the end of a given time horizon, the weighted sum of completion times and the number of auxiliary resource moves. The first criterion is maximized, while the two others are minimized. The first and the third criteria are not classical in scheduling theory, but are justified in industrial settings. The complexity of the problem with each of the new criteria is characterized. Integer linear programming models are also proposed and numerical experiments are conducted to analyze their behavior.