.png){kind=icon}
.png){kind=icon}
Return
Robust makespan minimisation in identical parallel machine scheduling problem with interval data
.png){kind=icon}
PRE
AI
DOI：10.1080/00207543.2012.751510.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Parallel machine scheduling problems are commonly encountered in a wide variety of manufacturing environments and have been extensively studied. This paper addresses a makespan minimisation scheduling problem on identical parallel machines, in which the specific processing time of each job is uncertain, and its probability distribution is unknown because of limited information. In this case, the deterministic or stochastic scheduling model may be unsuitable. We propose a robust (min-max regret) scheduling model for identifying a robust schedule with minimal maximal deviation from the corresponding optimal schedule across all possible job-processing times (called scenarios). These scenarios are specified as closed intervals. To solve the robust scheduling problem, which is NP-hard, we first prove that a regret-maximising scenario for any schedule belongs to a finite set of extreme point scenarios. We then derive two exact algorithms to optimise this problem using a general iterative relaxation procedure. Moreover, a good initial solution (optimal schedule under a mid-point scenario) for the aforementioned algorithms is discussed. Several heuristics are developed to solve large-scale problems. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.
Keywords:
makespan minimisation
identical parallel machines
min-max regret
uncertain processing times
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.3
Papers:
1.1W
Citations:
3.7W