具有退化工件和工期窗口安排的排序问题

doi:10.12005/orms.2015.0128

运筹与管理 ›› 2015, Vol. 24 ›› Issue (4): 116-121.DOI: 10.12005/orms.2015.0128

具有退化工件和工期窗口安排的排序问题

刘春来¹, 王建军¹, 赵传立²

1.大连理工大学系统工程研究所,辽宁大连 116023;
2.沈阳师范大学数学与系统科学学院,辽宁沈阳 110034

收稿日期:2013-11-09 出版日期:2015-08-12
作者简介:刘春来(1986-),男,博士研究生,研究方向:排序理论与算法,干扰管理;王建军(1977-),男,副教授,博士,研究方向:干扰管理、电子商务与物流管理;赵传立(1958-),男,教授,博士,研究方向:组合最优化。
基金资助:
国家自然科学基金资助项目(71271039;70902033);教育部“新世纪优秀人才支持计划”项目(NCET-13-0082);中央高校基本科研业务费专项资金资助项目(DUT14YQ211)

Common Due-window Assignment and Scheduling Problems with Deteriorating Jobs

LIU Chun-lai¹, WANG Jian-jun¹, ZHAO Chuan-li²

1.Institute of Systems Engineering, Dalian University of Technology, Dalian 116023, China;
2.School of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, China

Received:2013-11-09 Online:2015-08-12

摘要/Abstract

摘要： 针对具有退化工件的排序模型,考虑了单机排序和两台机器流水作业的工期窗口安排问题,在这一模型中,工件的加工时间是与其开工时间和退化率有关的一个线性函数。目标是找到一个最优排序和确定工期窗口的开始时间及大小以便最小化所有工件的费用函数,费用函数由四部分组成:提前、延误、工期窗口开始时间和工期窗口大小。对所研究的单机问题,详细地讨论了符合现实情况的几种类型问题,并得到了问题的最优解;对两台机器流水作业问题,给出了多项式算法。

关键词: 排序, 工期窗口, 退化工件, 提前-延误

Abstract: This paper is devoted to a scheduling problem with simple linear deterioration, that is, the processing time of a job is a simple linear function of its starting time and its deterioration rate. We consider the common due-window assignment problem for the single machine and two machine flow shop. The goal is to schedule the jobs and the due-window so as to minimize the highest cost among all the jobs. The objective function contains four cost components: earliness, tardiness, due-window starting time and size. By analyzing the properties of the optimal schedule, we obtain the due-window starting time and size. For the single machine and two-machine flow shop problems, we present a polynomial time solution respectively. Moreover, some special cases of the single machine are also discussed in detail.

Key words: scheduling, due-window assignment, deteriorating jobs, earliness-tardiness

中图分类号:

O223

刘春来, 王建军, 赵传立. 具有退化工件和工期窗口安排的排序问题[J]. 运筹与管理, 2015, 24(4): 116-121.

LIU Chun-lai, WANG Jian-jun, ZHAO Chuan-li. Common Due-window Assignment and Scheduling Problems with Deteriorating Jobs[J]. Operations Research and Management Science, 2015, 24(4): 116-121.

参考文献

[1] Alidaee B, Womer N K. Scheduling with time dependent processing times: review and extensions[J]. Journal of the Operational Research Society, 1999, 7(50): 711-720.
[2] Gawiejnowicz S. Time-dependent scheduling[M]. Berlin : Springer, 2008.
[3] Gupta J N D, Gupta S K. 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 processing[J]. Operations Research, 1990, 38(3): 495-498.
[5] Mosheiov G. Scheduling jobs under simple linear deterioration[J]. Computers and Operations Research, 1994, 21(6): 653-659.
[6] Gordon V S, Potts C N, Strusevich V A, Whitehead J D. Single machine scheduling models with deterioration and learning: handling precedence constraints via priority generation[J]. Journal of Scheduling, 2008, 11(5): 357-370.
[7] Mosheiov G. A note on scheduling deteriorating jobs[J]. Mathematical and Computer Modelling, 2005, 41(8-9): 883-886.
[8] 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.
[9] Cheng T C E. Optimal common due-date with limited completion time deviation[J]. Computers and Operations Research, 1988, 15(2): 91-96.
[10] Liman S D, Panwalker S S, Thongmee S. Common due window size and location determination in a single machine scheduling problem[J]. Journal of the Operational Research Society, 1998, 49(9): 1007-1010.
[11] Mosheiov G, Sarig A. A due-window assignment problem with position-dependent processing times[J]. Journal of the Operational Research Society, 2008, 59(7): 997-1003.
[12] Wang J B, Yang D L, Hsu C J. Single-machine scheduling to minimize absolute value in maximum lateness with deteriorating jobs[J]. Advanced Materials Research, 2011, 201-203: 1054-1060.
[13] Yang S J, Yang D L, Cheng T C E. Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance[J]. Computers and Operations Research, 2010, 37(8): 1510-1514.
[14] Mosheiov G, Sarig A. Minmax scheduling problems with a common due-window[J]. Computers and Operations Research, 2009, 36(6): 1886-1892.
[15] Zhao C L, Zhang Q L, Tang H Y. Scheduling problems under linear deterioration[J]. Acta Automatica Sinica, 2003, 29(4): 530-535.

具有退化工件和工期窗口安排的排序问题

Common Due-window Assignment and Scheduling Problems with Deteriorating Jobs

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(2): 84-90.
[9]	杨兴雨, 林虹, 何锦安, 张永. 基于排序预测的带交易费用在线投资组合策略[J]. 运筹与管理, 2021, 30(2): 168-175.
[10]	郑斐峰, 宋沁睿, 徐寅峰, 刘明. 考虑加工速率相互干扰的平行机调度最优策略研究[J]. 运筹与管理, 2021, 30(12): 1-5.
[11]	陶希闻, 江文奇. 面向直觉模糊集排序能力提升的记分函数设计研究[J]. 运筹与管理, 2021, 30(11): 34-39.
[12]	朱佳玮, 王尔大, 孙文章. 基于蒙特卡洛模拟的滨海旅游环境承载力影响因素重要性排序研究——以大连滨海景区为例[J]. 运筹与管理, 2021, 30(10): 47-52.
[13]	董晓芳, 张良勇. 产品可靠寿命的最优排序集挑选设计[J]. 运筹与管理, 2021, 30(10): 53-56.
[14]	张琳彦, 陈鸣, 徐倩, 张健. 考虑非期望因素的决策单元排序:两阶段综合效率法[J]. 运筹与管理, 2021, 30(10): 57-63.
[15]	董晓芳, 张良勇. 排序集抽样下指数分布的产品可靠度研究[J]. 运筹与管理, 2020, 29(7): 99-104.