具有退化工件和老化效应的单机可拒绝排序问题

doi:10.12005/orms.2017.0142

运筹与管理 ›› 2017, Vol. 26 ›› Issue (6): 95-101.DOI: 10.12005/orms.2017.0142

具有退化工件和老化效应的单机可拒绝排序问题

刘春来, 王建军

大连理工大学管理与经济学部,辽宁大连 116023

收稿日期:2016-01-16 出版日期:2017-06-25
作者简介:刘春来(1986-),男,山东青岛人,博士研究生,研究方向为生产调度;王建军(1977-),男,河北保定人,教授,博士生导师,研究方向为生产运作及干扰管理。
基金资助:
国家自然科学基金资助项目(71271039,70902033);新世纪优秀人才支持计划资助项目(NCET-13-0082);国家创新研究群体科学基金资助项目(71421001)

Single-machine Scheduling with Deteriorating Jobs, Aging Effect and Rejection

LIU Chun-lai, WANG Jian-jun

Institute of Systems Engineering, Dalian University of Technology, Dalian 116023, China

Received:2016-01-16 Online:2017-06-25

摘要/Abstract

摘要： 研究同时具有退化工件和老化效应的单机可拒绝排序问题,即工件的实际加工时间是与其开工时间和所在位置有关的函数,同时生产商可以通过支付一定的处罚费用而拒绝加工某些工件。在生产加工过程中,考虑对机器进行选择性维修活动来提高加工的效率;机器进行维修活动后将恢复到初始状态,老化效应也将重新开始。目标是确定拒绝哪些工件、何时进行维修活动以及接受工件集中工件的次序,以便极小化接受加工工件的最大完工时间与拒绝加工工件总处罚费用的和。证明得到了所研究的问题是NP-难解的,并给出了解决问题的一个全多项式时间近似方案(FPTAS)算法。

关键词: 单机排序, 拒绝, 维修活动, FPTAS

Abstract: This paper studies a single-machine scheduling with deteriorating jobs and aging effect under rejection, that is, the actual processing time of a job is the function of its starting time and the position scheduled. At the same time, the producer can reject some jobs by paying the rejection penalty. During the whole processing, the optional maintenance activity is scheduled in order to improve the efficiency. After the maintenance activity, the machine will restore the initial condition; the aging effect will also restart. The objective is to determine which jobs are rejected, when to arrange the maintenance activity and the sequence of the accepted jobs so that the sum of the makespan of the accepted jobs and total rejection penalty of the rejected jobs is minimized. We firstly prove the problem is NP-hard in the strong sense,and then a fully polynomial time approximation scheme is presented.

Key words: single-machine scheduling, rejection, maintenance activities, FPTAS

中图分类号:

O 223

刘春来, 王建军. 具有退化工件和老化效应的单机可拒绝排序问题[J]. 运筹与管理, 2017, 26(6): 95-101.

LIU Chun-lai, WANG Jian-jun. Single-machine Scheduling with Deteriorating Jobs, Aging Effect and Rejection[J]. Operations Research and Management Science, 2017, 26(6): 95-101.

参考文献

[1] Gawiejnowicz S. Time-dependent scheduling[M]. Berlin: Springer, 2008.
[2] Biskup D. A state-of-the-art review on scheduling with learning effects[J]. European Journal of Operational Research, 2008, 188: 315-329.
[3] 刘春来,王建军,赵传立.具有退化工件和工期窗口安排的排序问题[J].运筹与管理,2015,24(4):116-121.
[4] 王杜娟,王建军,刘春来,王延章.具有恶化效应的新工件到达生产调度干扰管理[J].系统工程理论与实践,2015,35(2):368-380.
[5] 刘颖,张新功.具有学习效应的三层供应链排序问题[J].运筹学学报,2016,20(1):31-42.
[6] Gupta J N D, Gupta S K. Single facility scheduling with nonlinear processing times[J]. Computers & Industrial Engineering, 1988, 4: 387-393.
[7] 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: 56-64.
[8] Mosheiov G. Scheduling jobs with step-deterioration: minimizing makespan on a single-and multi-machine[J]. Computers and Industrial Engineering, 1995, 28: 869-879.
[9] Yang S J. Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration[J]. Computers and Industrial Engineering, 2012, 62: 271-275.
[10] Araghi M E, Jolai F, Rabiee M. Incorporating learning effect and deterioration for solving a SDST flexible job-shop scheduling problem with a hybrid meta-heuristic approach[J]. International Journal of Computer Integrated Manufacturing, 2014, 27: 733-746.
[11] 刘鹏,周晓哗,荣楠.带有学习效应和恶化工件的双代理调度问题[J].系统工程学报,2012,27(6):841-846.
[12] Low C Y, Lin W Y. Some scheduling problems with time-dependent learning effect and deteriorating jobs[J]. Applied Mathematical Modelling, 2013, 37: 8865-8875.
[13] Janiak A, Krysiak T, Trela R. Scheduling problems with learning and ageing effects: a survey[J]. Decision Making in Manufacturing Services, 2011, 5: 19-36.
[14] Rustogi K, Strusevich VA. Simple matching vs linear assignment in scheduling models with positional effects: a critical review[J]. European Journal of Operational Research 2012, 222: 393-407.
[15] Nyman D, Levitt J. Maintenance planning, scheduling and coordination[M]. New York: Industrial Press, 2010.
[16] Lodree Jr E J, Geiger C D. A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration[J]. European Journal of Operational Research, 2010, 201: 644-648.
[17] Rustogi K, Strusevich V. Single machine scheduling with time-dependent linear deterioration and rate-modifying maintenance[J]. Journal of the Operational Research Society, 2014, 1-16.
[18] Rustogi K, Strusevich V. Single machine scheduling with general positional deterioration and rate-modifying maintenance[J]. Omega, 2012, 40: 791-804.
[19] Ji M, Hsu C J, Yang D L. Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration[J]. Journal of Combinatorial Optimization, 2013, 26: 437-447.
[20] 刘春来,赵传立.工期窗口安排与具有退化效应和维修活动的单机排序[J].数学的实践与认识,2012,42(11):121-130.
[21] Susan A. Order acceptance and scheduling: a taxonomy and review[J]. European Journal of Operational Research, 2011, 212: 1-11.
[22] Cheng Y S, Sun S J. Scheduling linear deteriorating jobs with rejection on a single machine[J]. European Journal of Operational Research, 2009, 194: 18-27.
[23] Li S S, Yuan J J. Parallel-machine scheduling with deteriorating jobs and rejection[J]. Theoretical Computer Science, 2010, 411: 3642-3650.
[24] 高强,鲁习文.带有拒绝的单机和同型机排序问题[J].运筹学学报,2014,18(4):1-10.
[25] 王磊,张玉忠,柏庆国.单机带有可拒绝的供应链排序问题[J].系统科学与数学,2014,34(9):1044-1050.
[26] Gerstl E, Mosheiov G. Scheduling on parallel identical machines with job-rejection and position-dependent processing times[J]. Information Processing Letters, 2012, 112: 743-747.
[27] 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.
[28] Zhao C L, Yin Y Q, Cheng T C E, Wu C C. Single-machine scheduling and due date assignment with rejection and position-dependent processingtimes[J]. Journal of Industrial and Management Optimization, 2014, 10(3): 691-700.
[29] Shabtay D, Gaspar N, Kaspi M. A survey on offline scheduling with rejection[J]. Journal of Scheduling, 2013, 16: 3-28.
[30] Kovalyov M Y, Kubiak W. A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs[J]. Journal of Heuristics, 1998, 3: 287-297.
[31] Kovalyov M Y, Kubiak W. A fully polynomial approximation scheme for the weighted earliness-tardiness problem[J]. Operations Research, 1999, 47: 757-761.
[32] Ji M, Cheng T C E. Parallel-machine scheduling with simple linear deterioration to minimize total completion time[J]. European Journal of Operational Research, 2008, 188: 342-347.
[33] Ji M, Yang Q Y, Yao D L, Cheng T C E. Single-machine batch scheduling of linear deteriorating jobs[J]. Theoretical Computer Science, 2015, 580: 36-49.

具有退化工件和老化效应的单机可拒绝排序问题

Single-machine Scheduling with Deteriorating Jobs, Aging Effect and Rejection

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

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