[1]陈可嘉,王 潇.机器具有不可用时间间隔的两机流水车间调度问题求解性质[J].南京理工大学学报(自然科学版),2015,39(02):202-205.
 Chen Kejia,Wang Xiao.Property of solving two-machine flow shop scheduling with unavailable interval[J].Journal of Nanjing University of Science and Technology,2015,39(02):202-205.
点击复制

机器具有不可用时间间隔的两机流水车间调度问题求解性质
分享到:

《南京理工大学学报》(自然科学版)[ISSN:1005-9830/CN:32-1397/N]

卷:
39卷
期数:
2015年02期
页码:
202-205
栏目:
出版日期:
2015-04-30

文章信息/Info

Title:
Property of solving two-machine flow shop scheduling with unavailable interval
作者:
陈可嘉王 潇
福州大学 管理学院,福建 福州 350108
Author(s):
Chen KejiaWang Xiao
School of Management,Fuzhou University,Fuzhou 350108,China
关键词:
两机流水车间调度 不可用时间间隔 Johnson算法 最坏性能比
Keywords:
two-machine flow shop scheduling unavailable intervals Johnson algorithm worst-case performance ratio
分类号:
N945
摘要:
在实际制造环境中,机器由于随机故障或进行预防性维护等,在某些时间段内处于不可用状态,为此,该文研究了任意一台机器具有不可用时间间隔的两机流水车间调度问题,给出了使用Johnson算法得到问题最优解的条件,分析了将Johnson算法作为问题启发式算法的最坏性能比范围。该文研究结果为探索机器具有不可用时间间隔的两机流水车间调度问题的最优算法提供了理论依据。
Abstract:
In view of that a machine is unavailable due to breakdowns or preventive maintenances in the practical manufacturing environment,the two-machine flow shop scheduling problem with an unavailable interval on any machine is studied.The optimality condition of solving the problem by the Johnson algorithm is presented.The worst-case performance ratio of the Johnson algorithm as a heuristic is analyzed.The results provide the theoretical bases for exploring the optimal algorithm of the two-machine flow shop scheduling problem with an unavailable interval.

参考文献/References:

[1] Lee C Y.Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint[J].Operations Research Letters,1997,20(3):129-139.
[2]Lee C Y.Two-machine flowshop scheduling with availability constraints[J].European Journal of Operational Research,1999,114(2):420-429.
[3]Cheng T C E,Wang G Q.An improved heuristic for two-machine flowshop scheduling with an availability constraint[J].Operations Research Letters,2000,26(5):223-229.
[4]Cheng T C E,Liu Z H.Approximability of two-machine no-wait flowshop scheduling with availability constraints[J].Operations Research Letters,2003,31(4):319-322.
[5]Breit J.An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint[J].Information Processing Letters,2004,90(6):273-278.
[6]Breit J.A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint[J].Computers & Operations Research,2006,33(8):2143-2153.
[7] Allaoui H,Artiba A,Elmaghraby S E,et al.Scheduling of a two-machine flowshop with availability constraints on the first machine[J].International Journal of Production Economics,2006,99(1-2):16-27.
[8]Wang X L,Cheng T C E.Heuristics for two-machine flowshop scheduling with setup times and an availability constraint[J].Computers & Operations Research,2007,34(1):152-162.
[9]Wang X L,Cheng T C E.An approximation scheme for two-machine flowshop scheduling with setup times and an availability constraint[J].Computers & Operations Research,2007,34(10):2894-2901.
[10]Allaoui H,Lamouri S,Artiba A,et al.Simultaneously scheduling n jobs and the preventive maintenance on the two-machine flow shop to minimize the makespan[J].International Journal of Production Economics,2008,112(1):161-167.
[11]Yang D L,Hsu C J,Kuo W H.A two-machine flowshop scheduling problem with a separated maintenance constraint[J].Computers & Operations Research,2008,35(3):876-883.
[12]Hadda H,Dridi N,Gabouj S H.An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs[J].Quarterly Journal of Operations Research,2010,8(1):87-99.

备注/Memo

备注/Memo:
收稿日期:2013-04-02 修回日期:2015-02-02
基金项目:国家自然科学基金(70901021); 教育部新世纪优秀人才支持计划(NCET-11-0903)
作者简介:陈可嘉(1978-),男,博士,副教授,主要研究方向:工业工程,E-mail:kjchen@fzu.edu.cn。
引文格式:陈可嘉,王潇.机器具有不可用时间间隔的两机流水车间调度问题求解性质[J].南京理工大学学报,2015,39(2):202-205.
投稿网址:http://zrxuebao.njust.edu.cn
更新日期/Last Update: 2015-04-30