期刊文献+

退化条件下具有维修活动的单机排序问题 被引量:2

The Problems of Single-machine Scheduling with Rate-modifying Activities Under Deterioration
原文传递
导出
摘要 在现实的环境中,工件的加工时间可能与其在机器上的开工时间有关,工件的开工时间越晚其加工时间越长,这种现象称为"退化效应"(Deteriorateing effect)。针对机器具有退化效应和维修活动(Rate-modifying activity,RMA)的单机排序模型,考虑一个序列无关的,在简单线性退化条件下工件的加工时间与工件所处的位置有关的,并且可以在任务序列中安排多个维修活动(RMAs)的单机极小化最大完工时间问题。在这一问题中,机器在加工过程中产生退化使效率降低;然而,对机器进行维修活动能使机器的加工效率得到恢复,从而能够使排在维修活动后的工件的加工时间缩短。在对本文问题的模型进行分析和适当的假设后,利用分组平衡原则,证明了当维修活动的次数确定时,最优排序满足分组平衡原则;最后,在满足一定的条件下,解决了是否安排维修活动、安排的次数以及安排在工件排序中的位置以便使最大完工时间最小这一问题,并提出了一个多项式最优算法。本文的结果推广和改进了已有文献中的结论。 In the real word, the processing time of a job may be dependent on its starting time in a schedule and the later a job starts, the longer it takes to process, this phenomenon is called "deteriorateing effect". Aiming at the single-machine scheduling model, which is the integration of scheduling models with deteriorateing effect and scheduling models with a rate-modifying activity(RMA) , we explore a sequence-independent, single processor makespan problem with position-dependent processing times and several rate-modifying activities. In the model, the machine deteriorates during the processing procedure making the efficiency of processing jobs lower. However, the rate-modifying activity restores the processing efficiency of the machine so that the processing times of the jobs scheduled after the RMAs is shortened. After the analysis of this problem model and appropriate assumptions, we prove that when determining the number of rate-modifying activities, the optimal scheduling to meet the group balance principle. Finally, we resolve the question of whether to arrange RMA, the times of RMAs, and the position of RMA in the scheduling in order to minimize the makespan under certain conditions and provide a polynomial-time optimal algorithm. The results of this paper generalize and improve the conclusions of the existing reference.
出处 《重庆师范大学学报(自然科学版)》 CAS 2011年第4期6-10,15,共6页 Journal of Chongqing Normal University:Natural Science
基金 国家自然科学基金(No.10471096)
关键词 排序 单机 维修活动 退化 最大完工时间 single-machine rate-modifying activities deterioration makespan
  • 相关文献

参考文献13

  • 1Browne S, Yechiali U. Scheduling deteriorating jobs on a single processing[ J]. Operations Research, 1900,38 : 495- 498.
  • 2Mosheiov G. Scheduling jobs under simple linear deterioration [ J ]. Computers and Operations Research, 1994, 21 (6) : 653-659.
  • 3Gordon V S, Potts C N, Strusevich V A, et al. Single ma- chine scheduling models with deterioration and learning: handling precedence constraints via priority generation[ J]. J Sched,2008,11:357-370.
  • 4Cheng T C E, Ding Q, Lin B M T. A concise survey of scheduling with time-dependent processing times [ J ]. Euro- pean Journal of Operational Research ,2004,152( 1 ) : 1-13.
  • 5Mosheiov G. A note on scheduling deteriorating jobs [ J ]. Mathematical and Computer Modelling,2005,41 : 883-886.
  • 6Lee C Y, Leon V. Machine scheduling with a rate-modifying activity [ J ]. European Journal of-Operational Research, 2001,128: 119-128.
  • 7Mosheiov G, Sidney J B. New results on sequencing with rate modifications[J].INFOR,2004,41:155-163.
  • 8Moshelov G, Oron D. Due-date assignment and malntenanee activity scheduling problem[J].Mathematical and Computer Modeling,2006,44 : 1053-1057.
  • 9Panwalkar S S, Smith M L, Seidmann A. Common due date assignment to minimize total penalty for the one machine scheduling problem [ J ]. Operations Research, 1982,30: 391-399.
  • 10Zhao C L, Tang H Y, Cheng C D. Two-parallel machines scheduling with rate-modifying aetivities to minimize total completion time[J].European Journal of Operational Re- search ,2009,198 : 354-357.

二级参考文献8

共引文献1

同被引文献15

  • 1Bachman A, Janiak A. Scheduling jobs with position-de- pendent processing times[J]. The Journal of the Operation- al Research Society, 2004,55 : 257-264.
  • 2Biskup D. A state-of-the-art review on scheduling with learning effects [J]. European Journal of Operational Re- search, 2008,188 : 315-329.
  • 3Janiak A, Kovalyov M Y. Scheduling in a contaminated are- a:a model and polynomial algorithms[J]. European Journal of Operational Research, 2006,173 : 125-132.
  • 4Gawiejnowicz S. Time-Dependent scheduling[M]. Berlin: Springer, 2008.
  • 5Lee C Y, Leon V. Machine scheduling with a rate-modifying activity [J]. European Journal of Operational Research, 2001,128: 119-128.
  • 6Xue P F, Zhang Y L, Yu X Y. Single-machine scheduling with piece-rate maintenance and interval constrained posi-tion-dependent processing times[J]. Applied Mathematics and Computation, 2014,226 : 415-422.
  • 7Zhao C L, Tang H Y, Cheng C D. Two-parallel machines scheduling with rate-modifying activities to minimize total completion time[J]. European Journal of Operation Re- search, 2009,198 : 354-357.
  • 8Yang S J,Yang D L. Minimize the total completion time in single-machine scheduling aging/deteriorating effects and deteriorating maintenance activities [J ]. Computer and Mathematics with Applications, 2010,60 : 2161-2169.
  • 9Kabir R,Strusevich V A. Combining time and position de- pendent effects on a single machine subject to rate-modif-ying activities[J]. Omega, 2014,42 : 166-173.
  • 10Kuo W H, Yang D L. Minimizing the makespan in a sin- gle-machine scheduling problem with the cyclic process of an aging effect[J]. Journal of the Operational Research Society, 2008,59 :416-420.

引证文献2

二级引证文献5

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部