具有老化效应的单机共同工期安排和工件可拒绝排序问题

doi:10.12005/orms.2021.0215

运筹与管理 ›› 2021, Vol. 30 ›› Issue (7): 66-70.DOI: 10.12005/orms.2021.0215

具有老化效应的单机共同工期安排和工件可拒绝排序问题

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

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

收稿日期:2015-07-14 出版日期:2021-07-25
作者简介:刘春来(1986-),男,山东青岛人,讲师,博士,研究方向为调度理论与算法。
基金资助:
国家自然科学基金资助项目(71901084,71672019,71421001);教育部人文社科基金资助项目(19YJC630099);浙江省自然科学基金资助项目(LQ19G020010);中央高校基本科研业务费资助(DUT21RW406);浙江省属高校基本科研业务费资助(GK199900299012-210)

Due-date Assignment and Single Machine Scheduling with Aging Effect and Rejection

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:2015-07-14 Online:2021-07-25

摘要/Abstract

摘要： 研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。

关键词: 单机排序, 拒绝, 老化效应, 维修活动, 工期安排

Abstract: This paper considers a single-machine scheduling and due date assignment problem. During the processing horizon, the processing time of a job depends on its position in a processing sequence and its aging effect and jobs also can be rejected by incurring penalties. The objective is to divide the jobs into a set of accepted and a set of rejected jobs, determine the sequence of accepted jobs and the location of maintenance activity so as to minimize the sum of the accepted jobs costs of earliness, tardiness, due date and the total penalty of the rejected jobs. We first provide a polynomial-time algorithm to solve the problem by translating it into assignment problem. We then prove a unified problem can be solved in polynomial time. Finally, we provide polynomial-time dynamic programming algorithms for the special case of the problem.

Key words: single-machine scheduling, rejection, aging effect, maintenance activity, due date assignment

中图分类号:

O223

刘春来, 王建军. 具有老化效应的单机共同工期安排和工件可拒绝排序问题[J]. 运筹与管理, 2021, 30(7): 66-70.

LIU Chun-lai, WANG Jian-jun. Due-date Assignment and Single Machine Scheduling with Aging Effect and Rejection[J]. Operations Research and Management Science, 2021, 30(7): 66-70.

参考文献

[1] Bachman A, Janiak A. Scheduling jobs with position-dependent processing times[J]. Journal of the Operational Research Society, 2004, 55: 257-264.
[2] Lalla-Ruiz E. Modeling the parallel machine scheduling problem with step deteriorating jobs[J]. European Journal of Operational Research, 2016, 255: 21-33.
[3] Janiak A, Rudek R. Scheduling jobs under an aging effect[J]. Journal of the Operational Research Society, 2010, 61: 1041-1048.
[4] Rustogi K, Strusevich V A. Single machine scheduling with general positional deterioration and rate-modifying maintenance[J]. Omega, 2012, 40: 791-804.
[5] Zhao C L, Hsu C J, Cheng S R, Wu C C. Due date assignment and single machine scheduling with deteriorating jobs to minimize the weighted number of tardy jobs[J]. Applied Mathematics and Computation, 2014, 248: 503-510.
[6] Yue Q, Wan G H. Single machine SLK/DIF due window assignment problem with job-dependent linear deterioration effects[J]. Journal of the Operational Research Society, 2016, 67(6): 872-883.
[7] Lee C L, Leon V J. Machine scheduling with a rate-modifying activity[J]. European Journal of Operational Research, 2001, 128: 119-128.
[8] Zhao C L, Tang H Y. Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan[J]. Applied Mathematical Modelling, 2010, 34: 837-841.
[9] Yang S, Yang D L. Minimizing the makespan on single machine scheduling with aging effect and variable maintenance activities[J]. Omega, 2010, 38: 528-533.
[10] Panwalkar 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.
[11] 刘春来,赵传立.工期窗口安排与具有退化效应和维修活动的单机排序[J].数学的实践与认识,2012,42(11):121-130.
[12] Chang P C, Chen S H, Mani V. A note on due-date assignment and single machine scheduling with a learning/aging effect[J]. International Journal of Production Economics, 2009, 117: 142-149.
[13] Gordon V S, Tarasevich A A. A note: Common due date assignment for a single machine scheduling with the rate-modifying activity[J]. Computers & Operations Research, 2009, 36: 325-328.
[14] Yang S J, Hsu C J, Yang D L. Single-machine scheduling with due-date assignment and aging effect under a deteriorating maintenance activity consideration[J]. International Journal of Information and Management Sciences, 2010, 21: 177-195.
[15] Yin Y Q, Wu W H, Cheng T C E, Wu C C. Due-date assignment and single-machine scheduling with generalized position-dependent deteriorating jobs and deteriorating multi-maintenance activities[J]. International Journal of Production Research, 2014, 52: 2311-2326.
[16] Gordon V S, Proth J M, Chu C. A survey of the state-of-art of common due date assignment and scheduling research[J]. European Journal of Operational Research, 2002, 139: 1-25.
[17] Yin Y, Wang D J, Wu C C, Cheng T C E. CON/SLK due date assignment and scheduling on a single machine with two agents[J]. Naval Research Logistics, 2016, 63: 416-429.
[18] Engels D W, Karger D R, Kolliopoulos S G, et al. Techniques for scheduling with rejection[J]. Journal of Algorithms , 2003, 49: 175-191.
[19] Bartal Y, Leonardi S, Spaccamela A M, Sgall J, Stougie L. Multiprocessor scheduling with rejection[J]. SIAM Journal on Discrete Mathematics, 2000, 13: 64-78.
[20] Gordon V S, Strusevich V A. Single machine scheduling and due date assignment with positionally dependent processing times[J]. European Journal of Operational Research, 2009, 198: 57-62.
[21] Hsu C J, Yang S J, Yang D L. Two due date assignment problems with position-dependent processing time on a single-machine[J]. Computers & Industrial Engineering,2011, 60: 796-800.
[22] Shabtay D, Gaspar N, Yedidsion L. A bicriteria approach to scheduling a single machine with job rejection and positional penalties[J]. Journal of Combinatorial Optimization, 2012, 23: 395-424.
[23] Nian H, Mao Z Z. Single-machine scheduling with job rejection, deteriorating effects, and deteriorating maintenance activities[J]. Mathematical Problems in Engineering, 2013, 389120.
[24] Shabtay D, Gaspar N, Kaspi M. A survey on offline scheduling with rejection[J]. Journal of Scheduling, 2013, 16: 3-28.
[25] 刘春来,王建军.具有退化工件和老化效应的单机可拒绝排序问题[J].运筹与管理,2017,26(6):95-101.

具有老化效应的单机共同工期安排和工件可拒绝排序问题

Due-date Assignment and Single Machine Scheduling with Aging Effect and Rejection

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

[1]	金苗苗, 吴蒙洁, 罗文昌. 具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案[J]. 运筹与管理, 2021, 30(8): 87-92.
[2]	余英, 程明宝. 带学习效应和资源依赖的单机排序模型[J]. 运筹与管理, 2018, 27(1): 53-58.
[3]	刘春来, 王建军. 具有退化工件和老化效应的单机可拒绝排序问题[J]. 运筹与管理, 2017, 26(6): 95-101.
[4]	余英, 舒彤, 曾春花. 工件带简单线性恶化函数和共同交货期单机排序问题[J]. 运筹与管理, 2016, 25(1): 154-157.
[5]	张新功, 严广乐, 唐国春, 唐海波. 具有指数和位置学习效应的机器排序问题[J]. 运筹与管理, 2011, 20(2): 97-101.