|本期目录/Table of Contents|

[1]胡觉亮,王焕男,蒋义伟.带时间延迟的极小化总完工时间的单机排序问题[J].浙江理工大学学报,2014,31-32(自科1):83-87.
　HU Jue liang,WANG Huan nan,JIANG Yi wei.Single Machine Sequencing Problem of Minimization of TotalCompletion Time with Time Delay[J].Journal of Zhejiang Sci-Tech University,2014,31-32(自科1):83-87.
点击复制

带时间延迟的极小化总完工时间的单机排序问题()
分享到：

浙江理工大学学报[ISSN:1673-3851/CN:33-1338/TS]

卷:
第31-32卷
期数:
2014年自科1期
页码:
83-87
栏目:
(自科)数学及应用
出版日期:
2014-01-03

文章信息/Info

Title:
Single Machine Sequencing Problem of Minimization of TotalCompletion Time with Time Delay
文章编号:
O233
作者:
胡觉亮;  王焕男;  蒋义伟
浙江理工大学理学院, 杭州 310018
Author(s):
HU Jueliang;  WANG Huannan;  JIANG Yiwei
School of Sciences, Zhejiang SciTech University, Hangzhou 310018, China
关键词:
单台机;  时间延迟;  总完工时间;  算法设计与分析;  最优排序
分类号:
1673-3851 (2014) 01-0083-05
文献标志码:
A
摘要:
研究工件带有两道工序的单台机排序问题。在该问题中,工件的第一道工序先于第二道工序加工,并且第二道工序的开工时间与第一道工序的完工时间至少间隔一定的延迟时间,目标是极小化所有工件的总完工时间。文章考虑所有工件相同且两道工序的加工时间均为单位时间的情形。通过引入k连续加工的概念和分析最优解的性质,根据延迟时间的大小,分别设计了两个算法并证明了算法所得的排序为最优排序。

参考文献/References:

［1］ Orman A J, Potts C N. On the complexity of coupledtask scheduling［J］. Discrete Applied Mathematics, 1997, 72 (1): 141-154.
［2］ Leung J, Li H, Zhao H. Scheduling twomachine flow shops with exact delay［J］. International Journal of Foundations of Computer Science, 2007, 18(2): 341-360.
［3］ Ageev A A, Kononov A V. Approximation algorithms for scheduling problems with exact delays［C］ //Erlebach T, Kaklamanis C. 4th International Workshop, WAOA 2006, Lecture Notes in Computer Science. Berlin: Springer, 2007, 4368: 1-14.
［4］ Ageev A A, Kononov A V. Approximation algorithms for the single and twomachine scheduling problems with exact delays［J］. Operations Research Letters. 2007, 35(4): 533-540.
［5］ Yu W, Hoogeveen H, Lenstra J K. Minimizing makespan in a twomachine flow shop with delays and unittime operations is NPhard［J］. Journal of Scheduling, 2004, 7 (5): 333-348.
［6］ Huo Y, Li H, Zhao H. Minimizing total completion time in twomachine flow shops with exact delays［J］. Computers and Operations Research. 2009, 36(6): 2018-2030.
［7］ Glascock J, Hunter B. Minimizing total completion time in twomachine flow shops with exact delay using genetic algorithm & ant colony algorithm［C］//Rothlauf F. Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference, New York: ACM, 2009: 2733-2736.
［8］ Kern W, Nawijn W M. Scheduling multioperation jobs with time lags on a single machine［C］// Faigle U, Hoede C. Proceedings 2nd Twente Workshop on Graphs and Combinatorial Optimization. Enschede: University of Twente, 1991.
［9］ Dell Amico  M. Shop problems with two machines and time lags［J］. Operations Research, 1996, 44(5): 777-787.
［10］Dell Amico  M, Vaessens R J M. Flow and open shop scheduling on two machines with transportation times and machine independent processing times is NP hard［M］. Modena: Universita Degli Studi di Modena, 1996: 103-121.
［11］ Johnson S M. Discussion: sequencing n jobs on two machines with arbitrary timelags［J］. Management Science, 1959, 5(3): 299-303.
［12］ Mitten L G. Sequencing n jobs on two machines with arbitrary timelags［J］. Management Science, 1959, 5(3): 293-298.
［13］ Yu  W. The twomachine flow shop problem with delays and the onemachine total tardiness problem［D］. Germany: Eindhoven University of Technology, 1996.

相似文献/References:

[1]胡觉亮,杨佳雯,苏晓彤,等.机器带周期性维护时段的加工与运输协同排序问题[J].浙江理工大学学报,2016,35-36(自科6):951.
　HU Jueliang,YANG Jiawen,SU Xiaotong,et al.Processing and Transportation Coordination Scheduling of Machine with Periodic Maintenance[J].Journal of Zhejiang Sci-Tech University,2016,35-36(自科1):951.

备注/Memo

备注/Memo:
收稿日期： 2012-10-31
基金项目： 国家自然科学基金(11001242,11071220)
作者简介： 胡觉亮(1958-),男,浙江杭州人,教授,大学本科,主要从事组合优化与数学建模的研究
更新日期/Last Update: 2013-12-30