基于退化效应的两台机器流水作业可拒绝排序

doi:10.15960/j.cnki.issn.1007-6093.2017.02.008

Abstract

Abstract:

In this paper, we consider the two-machine flow-shop scheduling with deterioration and rejection, in which each job's processing time is simple linear increasing function of its starting time. A job is either accepted and processed on the two machines in a flow-shop system, or rejected with a certain penalty having to be paid. The objective is to minimize the sum of the makespan of the accepted jobs plus the total penalty of the rejected jobs. We show that the problem is NP-hard and present a dynamic programming algorithm. Furthermore, we propose an optimal schedule for one special case.

Key words: scheduling, flow-shop, deterioration, rejection, NP-hard

MIAO Cuixia, MENG Fanxiao. Two-machine flow-shop scheduling with deterioration and rejection[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2017.02.008.

References

[1] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey [J]. Annals of Discrete Mathematics, 1979, 5: 287-326.

[2] Gupta G N D, Gupta S K. Single facility scheduling with nonlinear processing times [J]. Computers and Industrial Engineering, 1988, 14: 387-393.

[3] Browne S, Yechiali U. Scheduling deteriorating jobs on a single processor [J]. Operations Research, 1990, 38(3): 495-498.

[4] Mosheiov G. Scheduling jobs under simple linear deterioration [J]. Computers and Operations Research, 1994, 21: 653-659.

[5] 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-13.

[6] Gawiejnowicz S. Time-Dependent Scheduling [M]. Berlin: Springer, 2008.

[7] Wang J B, Wang J J. Single-machine scheduling problems with precedence constraints and simple linear deterioration [J]. Applied Mathematical Modelling, 2015, 39: 1172-1182.

[8] Bartal Y, Leonardi S, Marchetti-Spaccamela A, et al. Multiprocessor scheduling with rejection [J]. SIAM Journal Discrete Mathematics, 2000, 13: 64-78.

[9] Shabtay D, Gaspar N, Kaspi M. A survey on offline scheduling with rejection [J]. Journal of Scheduling, 2013, 16: 3-28.

[10] Choi B C, Chung J. Two-machine flow shop scheduling problem with an outsourcing option [J]. European Journal of Operational Research, 2011, 213: 66-72.

[11] Shabtay D, Gaspar N. Two-machine flow-shop scheduling with rejection [J]. Computers and Operations Research, 2012, 39: 1087-1096.

[12] Zhang L Q, Lu L F, Li S S. New results on two-machine flow-shop scheduling with rejection [J]. Journal of Combinatorial Optimization, 2016, 31: 1493-1504.

[13] Cheng Y S, Sun S T. Scheduling linear deteriorating jobs with rejection on a single machine [J]. European Journal of Operational Research, 2009, 194: 18-27.

[14] Li S S, Yuan J J. Parallel-machine scheduling with deteriorating jobs and rejection [J]. Theoretical Computer Science, 2010, 411: 3642-3650.

[15] Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-completeness [M]. San Francisco: Freeman, 1979.

[16] Johnson S M. Optimal two-and-three-stage production schedules with set-up times included [J]. Naval Research Logistics Quarter, 1954, 1: 61-68.

Two-machine flow-shop scheduling with deterioration and rejection

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[2]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[3]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[4]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[5]	GOU Yan, DAI Qin, ZHANG Xingong. Scheduling problem with time-and-position-dependent effect on two parallel machines environments [J]. Operations Research Transactions, 2019, 23(4): 86-94.
[6]	LI Ganggang, LU Xiwen. An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time [J]. Operations Research Transactions, 2019, 23(4): 95-104.
[7]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[8]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[9]	ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74.
[10]	CHEN Qiuhong, ZHANG Xingong. Two-agent preemptive scheduling of jobs with fixed time windows problem about total tardiness on a single machine [J]. Operations Research Transactions, 2019, 23(1): 61-71.
[11]	PENG Nannan, ZHANG Yuzhong, BAI Qingguo, WANG Chengfei. Online batch scheduling problem on uniform machines with agreeable processing times [J]. Operations Research Transactions, 2019, 23(1): 111-118.
[12]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[13]	JIANG Yanjun, XU Dachuan, ZHANG Dongmei. An approximation algorithm for the squared metric dynamic facility location problem [J]. Operations Research Transactions, 2018, 22(3): 49-58.
[14]	ZHAO Xiaocheng, LI Dagang. Parallel machine scheduling with machine and human eligibility restrictions [J]. Operations Research Transactions, 2018, 22(3): 99-108.
[15]	LI Ying, QIAO Longliang, ZHENG Feifeng. A study of online berth and quay crane integrated allocation problem with lookahead ability [J]. Operations Research Transactions, 2018, 22(3): 28-36.