具有学习和退化效应的单机干扰管理问题
|
摘要
针对工件同时具有学习和退化效应、机器具有可用性限制这一问题,建立可预见性单机干扰管理模型。在这一模型中,工件的加工时间是既与工件所排的加工位置又与工件开始加工的时间有关的函数。同时,在生产过程中由于机器发生故障或定期维修等扰动事件导致机器在某段时间内不能加工工件。目标是在同时考虑原目标函数和由扰动造成的偏离函数的情况下,构建一个新的最优时间表序列。根据干扰度量函数的不同研究了两个问题,第一个问题的目标函数是极小化总完工时间与总误工时间的加权和;第二个问题的目标函数是极小化总完工时间与总提前时间的加权和。对于所研究的问题,首先证明了最优排序具有的性质,然后建立了相应的拟多项式时间动态规划算法。
Aimed at the scheduling problem of machine availability constraint with learning and deteriorating effect,a predictable single machine disruption model is established. In the model,the processing time of a job is a function of its starting time and its position. Moreover,the machine could be unavailable for breakdown or periodic maintenance. Because of the machine disruption,the original schedule may become infeasible or too far from optimal. The objective is to create the new schedule that takes into account both the original objective function and a measure of deviation from the original schedule. Depending on the different measurement function,we study two versions of the problem. In the first one,the objective is weighted sum of total completion time and total tardiness while in the second one,the objective is weighted sum of total completion time and total earliness. For the problems,we first prove some properties of the optimal schedule and then dynamic programming algorithms are proposed.
Aimed at the scheduling problem of machine availability constraint with learning and deteriorating effect,a predictable single machine disruption model is established. In the model,the processing time of a job is a function of its starting time and its position. Moreover,the machine could be unavailable for breakdown or periodic maintenance. Because of the machine disruption,the original schedule may become infeasible or too far from optimal. The objective is to create the new schedule that takes into account both the original objective function and a measure of deviation from the original schedule. Depending on the different measurement function,we study two versions of the problem. In the first one,the objective is weighted sum of total completion time and total tardiness while in the second one,the objective is weighted sum of total completion time and total earliness. For the problems,we first prove some properties of the optimal schedule and then dynamic programming algorithms are proposed.
引文
[1] Browne S,Yechiali U. Scheduling deteriorating jobs on a single processing[J]. Operations Research,1990,38:495-498.
[2] Gupta J N D,Gupta S K. Single facility scheduling with nonlinear processing times[J]. Computers&Industrial Engineering,1988,4(14):387-393.
[3] Kunnathur A S,Gupta S K. Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem[J]. European Journal of Operational Research,1990,1(47):56-64.
[4] Mosheiov G. Scheduling jobs with step-deterioration:minimizing makespan on a single-and multi-machine[J].Computers and Industrial Engineering, 1995, 28:869-879.
[5] Gawiejnowicz S. Time-dependent scheduling[M].Springer,2008.
[6] Cheng T C E,Ding Q,Lin B M T. A concise survey of scheduling with time-dependent processing times[J].European Journal of Operational Research,2004,152(1):1-13.
[7] Biskup D. Single-machine scheduling with learning considerations[J]. European Journal of Operational Research,1999,115:173-178.
[8] Biskup D. A state-of-the-art review on scheduling with learning effects[J]. European Journal of Operational Research,2008,188:315-329.
[9] Lee W C. A note on deteriorating jobs and learning in single-machine scheduling problems[J]. International Journal of Business and Economics, 2004, 1(3):83-89.
[10] Wang J B,Guo D. A due-date assignment problem with learning effect and deteriorating jobs[J]. Applied Mathematical Modelling,2010,34:309-313.
[11] Yang D L,Kuo W H. Single-machine scheduling with both deterioration and learning effects[J]. Annals of Operations Research,2009,172(1):315-327.
[12] Cheng M B,Sun S J. The single-machine scheduling problems with deteriorating jobs and learning effect[J].Zhejiang University SCIENCE A, 2006, 7(4):597-601.
[13] Kacem I. Approximation algorithm for the weighted flowtime minimization on a single machine with a fixed nonavailability interval[J]. Computers&Industrial Engineering,2008,54:401-410.
[14]杨善林,马英,鲁付俊.带不可用时间段的单机调度问题的启发式算法[J].系统工程学报,2011,26(4):500-506.
[15] Kacem I,Chu C,Souissi A. Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times[J]. Computers and Operations Research,2008,35(3):827-844.
[16] Ji M,Yong H,Cheng T C E. Scheduling linear deteriorating jobs with an availability constraint on a single machine[J]. Theoretical Computer Science, 2006,362:115-126.
[17]马英,左春荣,杨善林.带不可用时间段和恶化加工时间的单机调度[J].系统工程学报,2010,25(3):371-378.
[18] Zhang M J,Luo C X. Parallel-machine scheduling with deteriorating jobs,rejection and a fixed non-availability interval[J]. Applied Mathematics and Computation,2013,224:405-411.
[19] Qi X,Bard J F,Yu G. Disruption management for machine scheduling:the case of SPT schedules[J].International Journal of Production Economics,2006,103:166-184.
[20]刘锋,王建军,杨德礼,崔晓聪.加工能力受限的单机干扰管理研究[J].管理工程学报,2012,2(26):191-196.
[21]刘锋,王建军,杨德礼,何平.加权折扣单机排序干扰管理模型和算法研究[J].管理科学,2012,1(25):99-108.
[22] Lee C Y,Yu G. Parallel-machine scheduling under potential disruption[J]. Optimization Letters,2008,2(1):27-37.
[23] Tang L X,Zhang Y Y. Parallel machine scheduling under the disruption of machine breakdown[J]. Industrial&Engineering Chemistry Research, 2009, 48(14):6660-6667.
[24]胡祥培,张漪,丁秋雷,王旭坪.干扰管理模型及其算法的研究进展[J].系统工程理论与实践,2008,28(10):40-46.
[25] Ouelhadj D,Petrovic S. A survey of dynamic scheduling in manufacturing systems[J]. Journal of scheduling,2009,12(4):417-431.
[26] Khodke P M,Bhongade A S. Real-time scheduling in manufacturing system with machining and assembly operations:a state of art[J]. International Journal of Production Research,2013:1-13.
[27] Zhao C L,Tang H Y. Rescheduling problems with deteriorating jobs under disruptions[J]. Applied Mathematical Modelling,2010,34:238-243.
[2] Gupta J N D,Gupta S K. Single facility scheduling with nonlinear processing times[J]. Computers&Industrial Engineering,1988,4(14):387-393.
[3] Kunnathur A S,Gupta S K. Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem[J]. European Journal of Operational Research,1990,1(47):56-64.
[4] Mosheiov G. Scheduling jobs with step-deterioration:minimizing makespan on a single-and multi-machine[J].Computers and Industrial Engineering, 1995, 28:869-879.
[5] Gawiejnowicz S. Time-dependent scheduling[M].Springer,2008.
[6] Cheng T C E,Ding Q,Lin B M T. A concise survey of scheduling with time-dependent processing times[J].European Journal of Operational Research,2004,152(1):1-13.
[7] Biskup D. Single-machine scheduling with learning considerations[J]. European Journal of Operational Research,1999,115:173-178.
[8] Biskup D. A state-of-the-art review on scheduling with learning effects[J]. European Journal of Operational Research,2008,188:315-329.
[9] Lee W C. A note on deteriorating jobs and learning in single-machine scheduling problems[J]. International Journal of Business and Economics, 2004, 1(3):83-89.
[10] Wang J B,Guo D. A due-date assignment problem with learning effect and deteriorating jobs[J]. Applied Mathematical Modelling,2010,34:309-313.
[11] Yang D L,Kuo W H. Single-machine scheduling with both deterioration and learning effects[J]. Annals of Operations Research,2009,172(1):315-327.
[12] Cheng M B,Sun S J. The single-machine scheduling problems with deteriorating jobs and learning effect[J].Zhejiang University SCIENCE A, 2006, 7(4):597-601.
[13] Kacem I. Approximation algorithm for the weighted flowtime minimization on a single machine with a fixed nonavailability interval[J]. Computers&Industrial Engineering,2008,54:401-410.
[14]杨善林,马英,鲁付俊.带不可用时间段的单机调度问题的启发式算法[J].系统工程学报,2011,26(4):500-506.
[15] Kacem I,Chu C,Souissi A. Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times[J]. Computers and Operations Research,2008,35(3):827-844.
[16] Ji M,Yong H,Cheng T C E. Scheduling linear deteriorating jobs with an availability constraint on a single machine[J]. Theoretical Computer Science, 2006,362:115-126.
[17]马英,左春荣,杨善林.带不可用时间段和恶化加工时间的单机调度[J].系统工程学报,2010,25(3):371-378.
[18] Zhang M J,Luo C X. Parallel-machine scheduling with deteriorating jobs,rejection and a fixed non-availability interval[J]. Applied Mathematics and Computation,2013,224:405-411.
[19] Qi X,Bard J F,Yu G. Disruption management for machine scheduling:the case of SPT schedules[J].International Journal of Production Economics,2006,103:166-184.
[20]刘锋,王建军,杨德礼,崔晓聪.加工能力受限的单机干扰管理研究[J].管理工程学报,2012,2(26):191-196.
[21]刘锋,王建军,杨德礼,何平.加权折扣单机排序干扰管理模型和算法研究[J].管理科学,2012,1(25):99-108.
[22] Lee C Y,Yu G. Parallel-machine scheduling under potential disruption[J]. Optimization Letters,2008,2(1):27-37.
[23] Tang L X,Zhang Y Y. Parallel machine scheduling under the disruption of machine breakdown[J]. Industrial&Engineering Chemistry Research, 2009, 48(14):6660-6667.
[24]胡祥培,张漪,丁秋雷,王旭坪.干扰管理模型及其算法的研究进展[J].系统工程理论与实践,2008,28(10):40-46.
[25] Ouelhadj D,Petrovic S. A survey of dynamic scheduling in manufacturing systems[J]. Journal of scheduling,2009,12(4):417-431.
[26] Khodke P M,Bhongade A S. Real-time scheduling in manufacturing system with machining and assembly operations:a state of art[J]. International Journal of Production Research,2013:1-13.
[27] Zhao C L,Tang H Y. Rescheduling problems with deteriorating jobs under disruptions[J]. Applied Mathematical Modelling,2010,34:238-243.