带有学习效应和机器可用性限制的排序问题

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (6): 1372-1375.

带有学习效应和机器可用性限制的排序问题

王纯, 赵传立

沈阳师范大学数学与系统科学学院, 辽宁, 沈阳, 110034

收稿日期:2008-01-21 修回日期:2008-03-19 出版日期:2009-06-20 发布日期:2010-01-03
作者简介:王纯(1983- ),女,硕士研究生,主要研究方向为排序理论与算法.E-mail:wangchun19830528@yahoo.com.cn
基金资助:
国家自然科学基金项目资助课题(10471096)

Scheduling problems with learning effect and availability constraint

WANG Chun, ZHAO Chuan-li

School of Mathematics and Systems Science, Shenyang Normal Univ., Shenyang 110034, China

Received:2008-01-21 Revised:2008-03-19 Online:2009-06-20 Published:2010-01-03

摘要/Abstract

摘要： 针对单机和两台机器的平行机排序问题,建立了机器具有学习效应和可用性限制的排序模型。在这个模型中,机器具有学习效应。在学习效应下,工件的加工时间与所排位置有关,对于需要在同台机器上加工的工件,工件随位置的靠后其实际的加工时间减少。同时由于定期维修等原因而导致机器在某段时间内不能加工工件。考虑了目标函数为极小化总完工时间的单机和两台机器的平行机问题。对于机器在任意时间进行维修的一般情况给出了动态规划算法,通过数值例子说明了算法的有效性,对机器在使用前进行维修的特殊情况给出了多项式算法。

Abstract: Aiming at the scheduling problems of the single machine and two parallel machines,a model of scheduling problems with learning effect and an availability constraint is established.In the model,the machines have learning effect.By the learning effect,the processing time of jobs is defined as the function of their positions in a sequence,and the jobs to be processed on the same machine,Their actual processing time is gradually reduced along with the order of their positions.Moreover,the machine could be unavailable for a specified period of time by periodic machine maintenance activity.That the objective function is to minimize the total completion time of single machine problems and two parallel machines problems is considered.A dynamic programming algorithm is provided for the machine maintenance in the common case at any time,and the validity of the algorithm is also illustrated by an example.A polynomial algorithm is given for the maintenance before the use of the machine in the special case.

中图分类号:

O223

王纯, 赵传立. 带有学习效应和机器可用性限制的排序问题[J]. Journal of Systems Engineering and Electronics, 2009, 31(6): 1372-1375.

WANG Chun, ZHAO Chuan-li. Scheduling problems with learning effect and availability constraint[J]. Journal of Systems Engineering and Electronics, 2009, 31(6): 1372-1375.

参考文献

[1] 唐国春,张峰,罗守成,等.现代排序论[M].上海:上海科学普及出版社,2003.
[2] Biskup D.Single-machine scheduling with learning considerations[J].European Journal of Operational Research,1999,115:173-178.
[3] Liu Jing,Sun Shijie,He Longmin.Some single machine scheduling problems with learning effect under consistent condition[J].运筹学学报,2003(7):21-28.
[4] Mosheiov G.Parallel machine scheduling with a learning effect[J].Journal of the Operational Research Society,2001,52:1165-1169.
[5] Mosheiov G,Sidney J B.Scheduling with general job-dependent learning curves[J].European Journal of Operational Research,2003,147:665-670.
[6] 马英,杨善林,储诚斌.机器在一段时间不可用条件下的单机调度问题[J].合肥工业大学学报,2007,30:1010-1014.
[7] Adiri I,Bruno J,Frostig E,et al.Single machine flow-time scheduling with a single breakdown[J].Acta Informatica,1989,26,679-696.
[8] 张丽华,涂摹生.一类单机维护调度问题研究[J].系统工程,2004,22:102-105.
[9] Lee C Y.Parallel machines scheduling with nonsimultancous machine available time[J].Discrete Applied Mathematics,1991,30:53-61.
[10] Lee C Y,Liman S D.Capacitated two-parallel machines scheduling to minimize sum of job completion timesEJ].DiscreteApplied Mathematics,1993,41:211-222.
[11] 李红英,苏纯洁.机器使用有限制的两台同类机排序[J].华东理工大学学报,2005,31:512-516.
[12] Lee C Y.Machine scheduling with an availability constraint[J].Journal of Global Optimization,1996(9):395-416.
[13] Ji Min,He Yong,Cheng T C E.Scheduling linear deteriorating jobs with an availability constraint on a single machine[J].Theoretical Computer Science,2006,362:115-126.
[14] Kovalyov M Y,Ng C T,Cheng T C E.Fixed interval scheduling:models,applications,computational complexity and algorithms[J].European Journal of Operational Research,2007,178:331-342.