Zhejiang Daxue xuebao. Lixue ban (Jan 2015)

Scheduling problems of a two-stage proportionate open shop(加工时间成比例的两阶段自由作业排序问题)

  • HUJueliang(胡觉亮),
  • LUOHui(罗惠),
  • DONGJianming(董建明)

DOI
https://doi.org/10.3785/j.issn.1008-9497.2015.01.015
Journal volume & issue
Vol. 42, no. 1
pp. 97 – 101

Abstract

Read online

对一类工件加工时间成比例的两阶段自由作业排序问题进行了研究.工件需要分别在包含m1和m2台平行机的两阶段中进行加工，工件在阶段间的加工满足自由作业环境要求，且相同工件在两阶段的加工时间相同，目标是极小化时间表长，即最后完工工件的完工时间.证明了当min{m1，m2} ≥ 2时该问题是NP-难的，给出了该问题的一个近似算法，并证明了该算法的最坏情况界不大于.得到了当min{m1，m2} =1时，该算法为问题的最优算法.

Keywords