.png){kind=icon}
Return
Scheduling two parallel machines with machine-dependent availabilities
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2016.01.021.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A two-parallel-machine scheduling problem with machine-dependent availabilities where one machine is subject to tool changes and the other is subject to periodic maintenance is considered. The objective is to determine the start time of each tool change activity and schedule all the jobs to the two machines such that the makespan is minimized. Due to the NP-hardness of the non-approximability of the problem, there does not exist any polynomial time approximation algorithm with a worst-case ratio less than 2 for the problem unless P = NP. To solve small sized and moderate sized instances of the problem, a mixed 0-1 programming model is proposed. To solve large sized instances of the problem, nine heuristic algorithms that employ two classical dispatching rules, two assignment mechanisms and a post optimization procedure are proposed. To evaluate the performance of the algorithms, some machine setting featured lower bounds are provided. Computational experiment shows that the average-case relative error ratio of the heuristic algorithm that based on the classical LPT rule, two assignment procedures and a post-optimization procedure is less than 8%, which implies that it is promising for problem and suitable for real-world application. (C) 2016 Elsevier Ltd. All rights reserved.
Keywords:
Scheduling
Tool change
Periodic maintenance
Makespan
Heuristic
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
Cited Papers
.png){kind=icon}
ShareSaveRadiation exposure to the patient and operating room personnel during percutaneous nephrolithotomy
PREAI
ShareSaveShareSaveSingle machine total completion time scheduling problem with workload-dependent maintenance duration
PREAI
ShareSaveShareSaveShareSave
View more