带有退化效应和序列相关运输时间的排序问题

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

Abstract

Abstract:

In this paper, the single-machine scheduling problem with simple deterioration and past-sequence-dependent (p-s-d) job delivery times is considered, in which the processing time of each job is a simple linear increasing function of its starting time. When the machine can process only one job at a time, firstly, the makespan, the total (weighted) completion time and the total lateness minimization problems are solvable in polynomial, the EDD rule is not an optimal solution to the maximum lateness minimization problem, and an optimal solution to the case where jobs have agreeable due dates and deteriorating rates is proposed. When the machine can process up to $b$ jobs simultaneously as a batch, i.e., the parallel-batch scheduling problems, two polynomial time optimal algorithms for the makespan minimization problem and the total weighted completion time minimization problem are presented, respectively.

Key words: scheduling, parallel-batch, deterioration, past-sequence-dependent delivery times

MIAO Cuixia, ZOU Juan. Scheduling with simple deterioration and past-sequence-dependent delivery times[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.04.007.

References

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

[2] Browne S, Yechiali U. Scheduling deteriorating jobs on a single processor [J]. Operations Research, 1990, 28: 495-498.

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

[4] 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.

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

[6] Cheng T C E, Yang S J, Yang D L. Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity [J]. International Journal of Production Economics, 2012, 135: 154-161.

[7] Wang J B, Wang M Z. Single-machine scheduling with nonlinear deterioration [J]. Optimization Letters, 2012, 6: 87-98.

[8] 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.

[9] Brucker P, Gladky A, Hoogeveen H, et al. Scheduling a batching machine [J]. Journal of Scheduling, 1998, 1: 31-54.

[10] Potts C N, Kovalyov M Y. Scheduling with batching: a review [J]. European Journal of Operational Research, 2000, 120: 228-249.

[11] Yuan J J, Qi X L, Lu L F, et al. Single machine unbounded parallel-batch scheduling [J]. European Journal of Operational Research, 2008, 186: 112-117.

[12] Li S S, Chen R X. Scheduling a bounded parallel-batching machine with incompatible job families and rejection [J]. Journal of the Operations Research Society of China, 2014, 2(4): 499-510.

[13] Wang C F, Zhang Y Z. On-line batch scheduling with known information in advance [J]. Operations Research Transactions, 2016, 20(1): 84-90.

[14] Koulamas C, Kyparisis G J. Single-machine scheduling problems with past-sequence-dependent delivery times [J]. International Journal of Production Economics, 2010, 126: 264-266.

[15] Liu M, Zheng F F, Chu C B, et al. New results on single-machine scheduling with past-sequence-dependent delivery times [J]. Theoretical Computer Science, 2012, 438: 55-61.

[16] Liu M, Zheng F F, Chu C B, et al. Single-machine scheduling with past-sequence-dependent delivery times and release times [J]. Information Processing Letters, 2012, 112: 835-838.

[17] Cheng T C E, Lee W C, Wu C C. Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times [J]. Applied Mathematical Modelling, 2011, 35: 1861-1867.

[18] Liu M, Zheng F F, Wang S J, et al. Scheduling deteriorating jobs with past-sequence-dependent delivery times [J]. International Journal of Production Economics, 2013, 44: 418-421.

[19] Shen L X, Wu Y B. Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects [J]. Applied Mathematical Modelling, 2013, 37: 5444-5451.

[20] Zhao C L, Tang H Y. Single machine scheduling problems with general position-dependent processing times and past-sequence-dependent delivery times [J]. Journal of Applied Mathematics Computer, 2014, 45: 259-274.

[21] Yin Y Q, Cheng T C E, Xu J Y, et al. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration [J]. Journal of Industral and Management Optimization, 2013, 9(2): 323-339.

[22] 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.

Scheduling with simple deterioration and past-sequence-dependent delivery times

PDF

Knowledge

Cited

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]	ZHAO Xiaocheng, LI Dagang. Parallel machine scheduling with machine and human eligibility restrictions [J]. Operations Research Transactions, 2018, 22(3): 99-108.
[14]	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.
[15]	HE Cheng, HAN Xinxin. Two-agent scheduling on an unbounded parallel-batching machine to minimize maximum cost and makespan [J]. Operations Research Transactions, 2018, 22(3): 109-116.