Scheduling equal length jobs with eligibility restrictions

被引：0
作者：
Juntaek Hong
Kangbok Lee
Michael L. Pinedo
机构：
[1] Pohang University of Science and Technology,Department of Industrial and Management Engineering
[2] New York University,Department of Information, Operations and Management Sciences, Stern School of Business
来源：
Annals of Operations Research | 2020年 / 285卷
关键词：
Parallel machine scheduling; Eligibility; Release date; Equal processing time jobs; Total completion time;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We consider the problem of scheduling independent jobs on identical parallel machines to minimize the total completion time. Each job has a set of eligible machines and a given release date, and all jobs have equal processing times. For the problem with a fixed number of machines, we determine its computational complexity by providing a polynomial time dynamic programming algorithm. We also present two polynomial time approximation algorithms along with their worst case analyses. Experiments with randomly generated instances show that the proposed algorithms consistently generate schedules that are very close to optimal.
引用
收藏
页码：295 / 314
页数：19
相关论文
共 31 条
  • [1] Baptiste P(2004)Ten notes on equal-processing-time scheduling Quarterly Journal of the Belgian, French and Italian Operations Research Societies 2 111-127
  • [2] Brucker P(1997)Complexity of scheduling problems with multi-purpose machines Annals of Operations Research 70 57-73
  • [3] Knust S(2008)Scheduling jobs with equal processing times and time windows on identical parallel machines Journal of Scheduling 11 229-237
  • [4] Timkovsky VG(1974)Scheduling independent tasks to reduce mean finishing time Communications of the ACM 17 382-387
  • [5] Brucker P(2006)Scheduling unit length jobs with parallel nested machine processing set restrictions Computers & Operations Research 33 620-638
  • [6] Jurisch B(1973)Minimizing average flow time with parallel machines Operations Research 21 846-847
  • [7] Krämer A(2004)Parallel machine scheduling under a grade of service provision Computers & Operations Research 31 2055-2061
  • [8] Brucker P(2009)Mixed integer programming formulations for single machine scheduling problems Computers & Industrial Engineering 56 357-367
  • [9] Kravchenko SA(2011)Parallel machine problems with equal processing times: a survey Journal of Scheduling 14 435-444
  • [10] Bruno J(2011)Scheduling jobs with equal processing times subject to machine eligibility constraints Journal of Scheduling 14 27-38
1234