具有学习和退化效应的单机干扰管理问题

doi:10.12005/orms.2019.0012

运筹与管理 ›› 2019, Vol. 28 ›› Issue (1): 94-100.DOI: 10.12005/orms.2019.0012

具有学习和退化效应的单机干扰管理问题

刘春来^1,2, 王建军²

1.杭州电子科技大学管理学院,浙江杭州 310018;
2.大连理工大学管理与经济学部,辽宁大连 116023

收稿日期:2014-09-04 出版日期:2019-01-25
作者简介:刘春来(1986-),男,山东青岛人,讲师,博士,研究方向:干扰管理、排序理论与算法;王建军(1977-),男,教授,博士生导师,研究方向:生产运作管理、电子商务与物流管理等。
基金资助:
国家自然科学基金资助项目(71672019,71271039,71421001);浙江省自然科学基金资助项目(LQ19G020010)

Disruption Management for Single Machine Scheduling with Learning and Deteriorating Effect

LIU Chun-lai^1,2, WANG Jian-jun²

1.School of Management, Hangzhou Dianzi University, Hangzhou 310018, China;
2.Faculty of Management and Economics, Dalian University of Technology, Dalian 116023, China

Received:2014-09-04 Online:2019-01-25

摘要/Abstract

摘要： 针对工件同时具有学习和退化效应、机器具有可用性限制这一问题,建立可预见性单机干扰管理模型。在这一模型中,工件的加工时间是既与工件所排的加工位置又与工件开始加工的时间有关的函数。同时,在生产过程中由于机器发生故障或定期维修等扰动事件导致机器在某段时间内不能加工工件。目标是在同时考虑原目标函数和由扰动造成的偏离函数的情况下,构建一个新的最优时间表序列。根据干扰度量函数的不同研究了两个问题,第一个问题的目标函数是极小化总完工时间与总误工时间的加权和;第二个问题的目标函数是极小化总完工时间与总提前时间的加权和。对于所研究的问题,首先证明了最优排序具有的性质,然后建立了相应的拟多项式时间动态规划算法。

关键词: 排序, 干扰管理, 学习效应, 退化工件, 动态规划

Abstract: 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.

Key words: scheduling, disruption management, learning effect, deteriorating jobs, dynamic programming

中图分类号:

O223

刘春来, 王建军. 具有学习和退化效应的单机干扰管理问题[J]. 运筹与管理, 2019, 28(1): 94-100.

LIU Chun-lai, WANG Jian-jun. Disruption Management for Single Machine Scheduling with Learning and Deteriorating Effect[J]. Operations Research and Management Science, 2019, 28(1): 94-100.

参考文献

[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 flow-time minimization on a single machine with a fixed non-availability 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.

具有学习和退化效应的单机干扰管理问题

Disruption Management for Single Machine Scheduling with Learning and Deteriorating Effect

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	金苗苗, 吴蒙洁, 罗文昌. 具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案[J]. 运筹与管理, 2021, 30(8): 87-92.
[2]	刘春来, 王建军. 具有老化效应的单机共同工期安排和工件可拒绝排序问题[J]. 运筹与管理, 2021, 30(7): 66-70.
[3]	王磊, 柏庆国, 任建峰. 具有两种运输方式选择的物流排序问题[J]. 运筹与管理, 2021, 30(6): 1-5.
[4]	易平涛, 董乾坤, 李伟伟. 残缺数据下动态随机算法及应用[J]. 运筹与管理, 2021, 30(6): 6-11.
[5]	李勇军, 蔡华权. 基于Shephard距离函数的DEA TOPSIS方法研究[J]. 运筹与管理, 2021, 30(5): 116-121.
[6]	陶玲玲, 尤天慧. 基于在线评价且考虑消费者类型的酒店排序方法[J]. 运筹与管理, 2021, 30(5): 122-128.
[7]	朱运霞, 昂胜, 杨锋. 基于SMAA和公共权重的决策单元效率评价与排序[J]. 运筹与管理, 2021, 30(4): 184-189.
[8]	董君, 叶春明. 具有学习效应的半导体晶圆制造绿色车间调度问题研究[J]. 运筹与管理, 2021, 30(4): 217-223.
[9]	周丽, 杨江龙. 基于遗传算法的多通道密集式移动货架订单拣选研究[J]. 运筹与管理, 2021, 30(2): 84-90.
[10]	杨兴雨, 林虹, 何锦安, 张永. 基于排序预测的带交易费用在线投资组合策略[J]. 运筹与管理, 2021, 30(2): 168-175.
[11]	郑斐峰, 宋沁睿, 徐寅峰, 刘明. 考虑加工速率相互干扰的平行机调度最优策略研究[J]. 运筹与管理, 2021, 30(12): 1-5.
[12]	陶希闻, 江文奇. 面向直觉模糊集排序能力提升的记分函数设计研究[J]. 运筹与管理, 2021, 30(11): 34-39.
[13]	朱佳玮, 王尔大, 孙文章. 基于蒙特卡洛模拟的滨海旅游环境承载力影响因素重要性排序研究——以大连滨海景区为例[J]. 运筹与管理, 2021, 30(10): 47-52.
[14]	董晓芳, 张良勇. 产品可靠寿命的最优排序集挑选设计[J]. 运筹与管理, 2021, 30(10): 53-56.
[15]	张琳彦, 陈鸣, 徐倩, 张健. 考虑非期望因素的决策单元排序:两阶段综合效率法[J]. 运筹与管理, 2021, 30(10): 57-63.