具有优先约束和加工时间依赖开工时间的单机排序问题

中国管理科学 ›› 2005, Vol. ›› Issue (2): 51-55.

具有优先约束和加工时间依赖开工时间的单机排序问题

王吉波

沈阳航空工业学院理学系, 沈阳, 110034

收稿日期:2004-06-04 修回日期:2005-03-03 出版日期:2005-04-28 发布日期:2012-03-07
基金资助:
教育部博士点基金资金资助项目(20020141013)

Single Machine Scheduling with Precedence Constraints and Processing Time Dependent on Starting Time

WANG Ji-Bo

Department of Science, Shenyang Institute of Aeronautical Engineering, Shenyang 110034, China

Received:2004-06-04 Revised:2005-03-03 Online:2005-04-28 Published:2012-03-07

摘要/Abstract

摘要： 研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。

关键词: 排序, 单机, 线性加工时间, 串并有向图, 加权总完工时间

Abstract: This paper deals with the total weighted completion time single machine scheduling with constraints of series-parallel digraph and processing time dependent on starting time.We apply Lawler’s algorithm which is used to solve the total weighted completion time single machine with constraints of series-parallel digraph to our problem by proving the following theorem.Under the condition that job processing time being a linear function of the starting time,jobs in the ρ-maximal initial set I of module M should be processed prior to other jobs in module M,and the schedule is the optimal if the jobs in set I aren’t be preempted by the jobs in N/I.

Key words: scheduling, single machine, linear processing time, series-parallel digraph, the total weighted completion time

中图分类号:

O223
C931

王吉波. 具有优先约束和加工时间依赖开工时间的单机排序问题[J]. 中国管理科学, 2005, (2): 51-55.

WANG Ji-Bo. Single Machine Scheduling with Precedence Constraints and Processing Time Dependent on Starting Time[J]. Chinese Journal of Management Science, 2005, (2): 51-55.

参考文献

[1] Alidaee B,Womer N K.Scheduling with time dependent processing times:review and extensions[J].Journal of the Operational Research Society,1999,50:711-720.
[2] Mosheiov G.V-shaped policies for scheduling deteriorating jobs[J].Operations Research,1991,39:979-991.
[3] Sundararaghavan P S,Kunnathur A S.Single machine scheduling with start time dependent processing times:some solvable cases[J].European Journal of Operational Research,1994,78:394-403.
[4] Browne S,Yechiali U.Scheduling deteriorating jobs on a single processor[J].Operations Research,1990,38:495-498.
[5] Mosheiov G.Scheduling jobs under simple linear deterioration[J].Computers and Operations Research,1994,21:653-659.
[6] Mosheiov G.Complexity analysis of job-shop scheduling with deteriorating jobs[J].Discrete Applied Mathematics,2002,117:195-209.
[7] 赵传立.若干新型排序问题算法研究[D].沈阳,东北大学博士论文,2003.
[8] Lawler E L.Sequencing jobs to minimize total weighted completion time subject to precedence constraints[J].Annals of Discrete Mathematics,1978,2:75-90.
[9] Sidney J B.Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs[J].Operations Research,23:283-298.
[10] 郭立夫,陆晓芳.m×n同序加工的生产周期算法[J].中国管理科学,1995,3(3):20-25.
[11] 张召生,刘家壮.大规模集成电路预烧作业中分批排序问题的数学模型[J].中国管理科学,2003,11(4):32-36.
[12] 李国富,叶飞帆.多功能机床环境下的Job shop问题研究[J].中国管理科学,2000,8(4):24-28.
[13] 陈伟达,达庆理.基于杂合遗传算法的工艺路线可变Job shop调度问题[J].中国管理科学,2001,9(4):25-29.
[14] 成龙,小冬,杨斌鑫.单机排序1|sp-graph|∑_wj(1-e-rCj)的最优算法[J].系统工程,2004,22(2):92-96.
[15] Wang J.-B.Xia Z.-Q.Scheduling jobs under dereasing linear deterioration[J].Information Processing Letters,2005,94:63-69.
[16] Wang J.-B.Xia Z.-Q.No-wait or no-idle permutation flowshop scheduling with dominating machines[J].Journal of Applied Mathematics and Computing,2005,17:419-432.