期刊文献+

加工时间成比例的两阶段自由作业排序问题

Scheduling problems of a two-stage proportionate open shop
下载PDF
导出
摘要 对一类工件加工时间成比例的两阶段自由作业排序问题进行了研究.工件需要分别在包含m1和m2台平行机的两阶段中进行加工,工件在阶段间的加工满足自由作业环境要求,且相同工件在两阶段的加工时间相同,目标是极小化时间表长,即最后完工工件的完工时间.证明了当min{m1,m2}≥2时该问题是NP-难的,给出了该问题的一个近似算法,并证明了该算法的最坏情况界不大于3/2-3/2(2min{m1,m2}+1).得到了当min{m1,m2}=1时,该算法为问题的最优算法. Scheduling problems of a two-stage proportionate open shop were considered, and the two stages of the open shop were formed with ml identical machines in the first stage and rn2 identical machines in the other stage. The processing time of each job at both stages were identical. The objective is to minimize the makespan, i. e. , to maximize the completion time of all jobs. We firstly prove that the problem is NP-hard when rain{m1, m2 }≥2. Then an approximationalgorithm with the worst-case performance ratio of 3/2-3/2(2min{m1,m2}+1 is also provided. Especially, when min{ m1 ,m2 } = 1, our study indicates that the algorithm is the optimal algorithm for the problerm.
出处 《浙江大学学报(理学版)》 CAS CSCD 北大核心 2015年第1期97-101,共5页 Journal of Zhejiang University(Science Edition)
基金 国家自然科学基金资助项目(11471286) 浙江省自然科学基金资助项目(LY13A010015) 浙江理工大学科研启动基金项目(13062171-Y)
关键词 两阶段自由作业排序问题 近似算法 最坏情况界 two-stage open shop scheduling approximation algorithm worst-case performance ratio
  • 相关文献

参考文献9

  • 1HOOGEVEEN J, LENSTRA J, VELTMAN B. Pre emptive scheduling in a two-stage multiprocessor flow shop is NP-hard[-J]. European Journal of Operational Research, 1996, 89(1) :172-175.
  • 2LEE C, VAIRAKTARAKIS G. Minimizing makespan in hybrid flowshops[J]. Operations Research Letters, 1994,16(3) : 149-158.
  • 3SCHUURMANA P, WOEGINGER G. Approxima- tion algorithms for the multiprocessor open shop scheduling problem[J]. Operations Research Letters, 1999,24(4) : 157-163.
  • 4SRIBAS I, LEISTEN R, FRAMINAN J. Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective[J]. Computers & Operations Research, 2010,37 (8) : 1439-1454.
  • 5RUIZ R, VAZQUEZ-RODRIGUEZ J. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010,205 ( 1 ) : 1-18.
  • 6CHEN B, STRUSEVICH V. Worst-case analysis of heuristics for open shops with parallel machines[,J]. European Journal of Operational Research, 1993,70 ( 3 ) : 379-390.
  • 7SCHUURMAN P, WOEGINGER G. Approximation algorithms for the multiprocessor open shop scheduling problem[J ]. Operations Research Letters, 1999,24 ( 4 ) : 157-163.
  • 8JANSEN K, SVIRIDENKO M. Polynomial time ap- proximation schemes for the multiprocessor open and flow shop scheduling problem[,JB. The Symposium on Theoretical Aspects of Computer Science, 2000, 177-0 : 455-465.
  • 9CHOI B, LEE K. Two-stage proportionate flexible flow shop to minimize the makespan[J]. Journal of Combinatorial Optimization, 2013,25 ( 1 ) : 123-134.

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部