Makespan minimization in preemptive two machine job shops

被引：0
作者：
S. V. Sevastianov
G. J. Woeginger
机构：
[1] Siberian Branch of the Russian Academy of Sciences,Institute of Mathematics
[2] Graz University of Technology,Institut für Mathematik
来源：
Computing | 1998年 / 60卷
关键词：
68Q25; 68C15; 90B35; Scheduling; approximation algorithm; worst-case analysis; job shop;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
In this note we investigate the NP-complete problem of minimizing the makespan in a preemptive two machine job shop. We present a polynomial time approximation algorithm with worst case ratio 3/2 for this problem, and we also argue that this is the best possible result that can be derived via our line of approach.
引用
收藏
页码：73 / 79
页数：6
相关论文
共 10 条
  • [1] Akers S. B.(1956)A graphical approach to production scheduling problems Oper. Res. 4 244-245
  • [2] Gonzalez T.(1978)Flowshop and jobshop schedules: complexity and approximation Oper. Res. 26 36-52
  • [3] Sahni S.(1969)Bounds on multiprocessing timing anomalies SIAM J. Appl. Math. 17 416-429
  • [4] Graham R. L.(1982)An efficient optimal algorithm for the two-machine, unit-time, jobshop, schedule-length problem Math. Oper. Res. 7 354-360
  • [5] Hefetz N.(1956)An extension of Johnson’s result on job lot scheduling Naval. Res. Log. Q. 3 201-203
  • [6] Adiri I.(1996)Improved approximation algorithm for shop scheduling problems SIAM. J. Comput. 23 617-632
  • [7] Jackson J. R.(undefined)undefined undefined undefined undefined-undefined
  • [8] Shmoys D. B.(undefined)undefined undefined undefined undefined-undefined
  • [9] Stein C.(undefined)undefined undefined undefined undefined-undefined
  • [10] Wein J.(undefined)undefined undefined undefined undefined-undefined
1