排序问题是机械制造业、计算机系统、管理科学中的一类重要问题。研究具有恶化工件的单机排序问题, 其中恶化工件指的是工件的实际加工时间是其开工时间的线性递增函数且所有工件的恶化率相同。每个工件具有不同的工期, 且为决策变量。目标是确定所有工件的一个排序和每个工件的工期使得目标函数为提前成本、延迟成本和工期机会成本的加权和最小。证明该问题的算法复杂性是多项式时间可解的, 并给出了如何求解该问题的最优算法。
关键词：
排序; 单机; 恶化工件; 工期; 算法
Scheduling is an important part in manufacturing industry, computer systems and management sciences.In this paper we study the single-machine due-dates assignment scheduling with deteriorating jobs, which means that the actual processing times of jobs are defined by increasing function of their starting times and the deteriorating rates of all jobs are identical.Associated with each job there is a due date, and a decision variable.The objective is to determine the optimal schedule and due-dates simultaneously to minimize the sum of earliness, tardiness and due dates.We verify that the problem of deterioration can be solved in polynomial time, and we also provide a polynomial time algorithm to solve the problem.
[1]唐国春, 张峰, 罗守成, 等.现代排序论[M].上海:上海科学普及出版社, 2003.
[2]Gawiejnowicz S.Time-Dependent Scheduling [M].Berlin:Springer-Verlag, 2008.
[3]Gupta JND, Gupta SK.Single facility scheduling with nonlinear processing times[J].Computers and Industrial Engineering, 1988, 14(4):387-393.
[4]Browne S, Yechiali U.Scheduling deteriorating jobs on a single processor[J].Operations Research, 1990, 38(3):495-498.
[5]Mosheiov G.V-Shaped policies to schedule deteriorating jobs[J].Operations Research, 1991, 39(6):979-991.
[6]Mosheiov G.Scheduling jobs under simple linear deterioration[J].Computers and Operations Research, 1994, 21(6):653-659.
[7]Bachman A, Janiak A.Minimizing maximum lateness under linear deterioration[J].European Journal of Operational Research, 2000, 126(3):557-566.
[8]赵传立, 张庆灵, 唐恒永.具有线性恶化加工时间的调度问题[J].自动化学报, 2003, 29(4):531-535.
[9]赵传立, 张庆灵, 唐恒永.一类线性加工时间单机调度问题[J].自动化学报, 2003, 29(5):703-708.
[10]Cheng TCE, Kang L, Ng CT.Due-date assignment and single machine scheduling with deteriorating jobs[J].Journal of the Operational Research Society, 2004, 55(2):198-203.
[11]Wu CC, Shiau YR, Lee WC.Single-machine group scheduling problems with deterioration consideration[J].Computers and Operations Research, 2008, 35(5):1652-1659.
[12]Oron D.Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times[J].Computers and Operations Research, 2008, 35(6):2071-2078.
[13]王爽, 赵传立.考虑恶化和学习效应的单机成组排序问题[J].系统工程与电子技术, 2008, 30(2):288-291.
[14]闫杨, 王大志, 汪定伟, 等.一类具有资源约束和恶化效应的单机成组排序问题[J].控制与决策, 2008, 23(12):1413-1416.
[15]王丹.具有老化效应的单机多目标排序问题[J].沈阳航空工业学院学报, 2009, 26(4):82-84.
[16]Ji M, Cheng TCE.Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan[J].European Journal of Operational Research, 2010, 202(1):90-98.
[17]Wang J-B, Wang J-J, Ji P.Scheduling jobs with chain precedence constraints and deteriorating jobs[J].Journal of the Operational Research Society, 2011, 62(9):1765-1770.
[18]Wang J-B, Huang X, Wu Y-B, et al.Group scheduling with independent setup times, ready times, and deteriorating job processing times[J].International Journal of Advanced Manufacturing Technology, 2012, 60(5-8):643-649.
[19]王吉波, 王建军, 何平.具有共同松弛时间的恶化型工件排序问题研究[J].大连理工大学学报, 2012, 52(6):932-936.
[20]Wang J-B, Wang M-Z.Minimizing makespan in three-machine flow shops with deteriorating jobs[J].Computers and Operations Research, 2013, 40(2):547-557.
[21]Wang X-R, Wang J-J.Single-machine scheduling with convex resource dependent processing times and deteriorating jobs[J].Applied Mathematical Modelling, 2013, 37(4):2388-2393.
[22]Seidmann A, Panwalkar SS, Smith ML.Optimal assignment of due-dates for a single processor scheduling problem[J].International Journal of Production Research, 1988, 19(4):393-399.
[23]Gordon VS, Proth JM, Chu CB.A survey of the state-of-the-art of common due date assignment and scheduling research[J].European Journal of Operational Research, 2002, 139(1):1-25.
