.png){kind=icon}
.png){kind=icon}
Return
Minimizing total completion time with machine-dependent priority lists
.png){kind=icon}
OA
AI
DOI：10.1016/j.ejor.2023.12.030.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider a natural, yet challenging variant of the parallel machine scheduling problem in which each machine imposes a preferential order over the jobs and schedules the jobs accordingly once assigned to it. We study the problem of minimizing the total completion time, distinguishing between identical and unrelated machines, machine -dependent and identical priority lists, or a constant number of different priority classes. Additionally, we consider the setting in which the priority list on a machine must satisfy longest processing time first. We resolve the computational complexity of the problem and provide a clear distinction between problems that are polynomial time solvable and APX-hard.
Keywords:
Scheduling
Total completion time
Priorities
Dynamic programming
Inapproximability
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W