带凸资源和恶化效应的单机松弛窗口排序

doi:10.12005/orms.2020.0178

摘要/Abstract

摘要： 研究带凸资源和恶化效应的单机窗口指派排序问题,其中窗口指的是松弛窗口,凸资源和恶化效应指的是工件的实际加工时间是其开始加工时间的线性函数,是其资源消耗量的凸函数。目标是确定工件的加工顺序,资源分配量以及窗口的开始加工时间和长度使其在总资源消耗费用(与窗口有关的排序费用)有上界限制的条件下,极小化与窗口有关的排序费用(总资源消耗费用)。获得了求解上述问题的最优算法,证明了该问题是多项式时间可解的。

关键词: 排序, 松弛窗口, 恶化效应, 凸资源

Abstract: In this paper we consider the single machine due window assignment scheduling problem with convex resource and deterioration effect, in which due window is a slack due window, and convex resource and deterioration effect mean that the actual processing time of a job is a linear function of its starting time and a convex function of resource consumption. The objective is to find the optimal schedule, the resource allocation of jobs and the starting time of slack due window and its size of due window, so as to minimize the schedule cost associated with the slack due window (the total resource consumption cost) when the total resource consumption cost (the schedule cost associated with the slack due window) is a given upper bound. The optimal algorithms are proposed, and we prove that this problem can be solved in polynomial time.

Key words: scheduling, slack due window, deterioration effect, convex resource

中图分类号:

O223

姜昆. 带凸资源和恶化效应的单机松弛窗口排序[J]. 运筹与管理, 2020, 29(7): 105-109.

JINAG Kun. Single Machine Slack Due Window Scheduling with Convex Resource and Deterioration Effect[J]. Operations Research and Management Science, 2020, 29(7): 105-109.

参考文献

[1] Ng C T,Wang J B, Cheng T C E, Liu L L. A branch-and-bound algorithm for solving a two-machine flow shop problem with deteriorating jobs[J]. Computers and Operations Research, 2010, 37: 83-90.
[2] Wang J B, Wang M Z. Minimizing makespan in three-machine flow shops with deteriorating jobs[J]. Computers and Operations Research, 2013, 40(2): 547-557.
[3] 王吉波,刘璐,许扬涛,郭倩.具有恶化工件的不同工期指派问题研究[J].沈阳航空航天大学学报,2013,30(5):83-87.
[4] 王吉波,郭苗苗,刘桓,李琳,王丹.具有依赖开工时间恶化工件的流水作业排序问题研究综述[J].沈阳航空航天大学学报,2016,33(3):1-10.
[5] 王吉波,赵伯来.具有独立调整时间和恶化效应的单机成组排序问题研究[J].沈阳航空航天大学学报,2017,34(4):82-87.
[6] Gawiejnowicz S. Time-dependent scheduling[M]. Springer, 2008.
[7] Shabtay D, Steiner G. A survey of scheduling with controllable processing times[J]. Discrete Applied Mathematics, 2007, 155: 1643-1666.
[8] Lu Y Y, Li G, Wu Y B, Ji P. Optimal due-date assignment problem with learning effect and resource-dependent processing times[J]. Optimization Letters, 2014, 8: 113-127.
[9] 罗成新,翟雯瑾.具有一般截断因子和资源约束的单机工期窗口排序问题[J].重庆师范大学学报(自然科学版),2017,34(4):1-7.
[10] 刘鹏,周晓晔,衣娜.带有减少线性恶化效应的双代理调度问题[J].系统工程学报,2011,26:387-392.
[11] Wei C M, Wang J B, Ji P. Single-machine scheduling with time-and-resource-dependent processing times[J]. Applied Mathematical Modeling, 2012, 36: 792-798.
[12] Wang X R, Wang J J. Single-machine scheduling with convex resource dependent processing times and deteriorating jobs[J]. Applied Mathematical Modelling, 2013, 37: 2388-2393.
[13] Wang X Y, Wang J J. Single-machine due date assignment problem with deteriorating jobs and resource-dependent processing times[J]. International Journal of Advanced Manufacturing Technology, 2013, 67: 255-260.
[14] Zhao C, Hsu C J, Wu W H, Cheng S R, Wu C C. Note on a unified approach to the single-machine scheduling problem with a deterioration effect and convex resource allocation[J]. Journal of Manufacturing Systems, 2016, 38: 134-140.
[15] 郭苗苗,闫萍,汪佳,王吉波.具有恶化效应和凸资源分配关系的单机排序问题[J].运筹与管理,2017,26(6):102-106.
[16] Wu Y B, Wan L, Wang X Y. Study on due-window assignment scheduling based on common flow allowance[J]. International Journal of Production Economics, 2015, 165: 155-157.
[17] Li G, Luo M L, Zhang W J, Wang X Y. Single-machine due-window assignment scheduling based on common flow allowance, learning effect and resource allocation[J]. International Journal of Production Research, 2015, 53: 1228-1241.
[18] Hardy G H, Littlewood J E, Polya G. Inequalities[M]. Cambridge: Cambridge University Press, 1934.