Due-Date Assignment on a Single Machine Scheduling Problem with Nonlinear Deterioration Function

Abstract:

The paper considers the due-date assignment problem with a non-linear deterioration in which the due dates are determined by the equal slack method. Here, the processing time of a job is defined by a non-linear function of total normal processing time of jobs in front of it in the sequence. The objective is to minimize the total tardiness penalties. According to the needs from the real world, the problem is divided into two cases, i.e., allowing with early jobs and no early jobs respectively. The related lemma, corollary and theorems for the problems are proposed and proved. At the same time, it shows that the problems in this paper can be solved in the polynomial times.

• Periodical: Advanced Materials Research (Volume 645)
• Pages: 280-284
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.645.280
• Online since: January 2013
• Authors: Hua Ping Wu, Min Huang, Vincent Cho, W.H. Ip, Xing Wei Wang
• Keywords: Deteriorating Jobs, Scheduling, Single-Machine, SLK due Date, Total Tardiness Penalties

References

[1] V. Gordon, J. Proth, C. Chu. A survey of the state-of-the-art of common due date assignment and scheduling research. Eur. J. Oper. Res. Vol. 139 (2002), pp.1-25.

DOI: 10.1016/s0377-2217(01)00181-3

[2] T. C. E. Cheng, L. Y. Kang, C. T. Ng. Due-date assignment and parallel-machine scheduling with deteriorating job. J. Oper. Res. Soc. Vol. 58 (2007), pp.1103-1108.

DOI: 10.1057/palgrave.jors.2602225

[3] B. Shirazi, H. Fazlollahtabar, N. Sahebjamnia. Minimizing Arbitrary Earliness/Tardiness Penalties with Common Due Date in Single-Machine Scheduling Problem Using a Tabu-Geno-Simulated Annealing. Mater. Manuf. Process. Vol. 25 (2010), pp.515-525.

DOI: 10.1080/10426910903365828

[4] C-J Hsu, S-J Yang, D-L Yang. Due-date assignment and optional maintenance activity scheduling problem with linear deteriorating jobs. J. Mar. Sci. Technol. Vol. 19 (2011), pp.97-100.

DOI: 10.51400/2709-6998.2141

[5] C-J Hsu, S-J Yang, D-L Yang. Two due date assignment problems with position-dependent processing time on a single-machine. Comput. Ind. Eng. Vol. 60 (2011), pp.796-800.

DOI: 10.1016/j.cie.2011.01.017

[6] W-H Kuo, D-L Yang. Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect. Eur. J. Oper. Res. Vol. 174 (2006), pp.1184-1190.

DOI: 10.1016/j.ejor.2005.03.020

[7] D. Wang, J-B Wang. Single-machine scheduling with simple linear deterioration to minimize earliness penalties. Int. J. Adv. Manuf. Technol. Vol. 46 (2010), pp.285-290.

DOI: 10.1007/s00170-009-2086-8

[8] G. I. Adamopoulos, C. P. Pappis. Scheduling jobs with different, job-dependent earliness and tardiness penalties using the SLK method. Eur. J. Oper. Res. Vol. 88 (1996), pp.336-344.

DOI: 10.1016/0377-2217(94)00191-x

[9] R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan. Optimization and approximation in the deterministic sequencing and scheduling: a survey. Ann. Discret. Math. Vol. 5 (1979), pp.287-326.

DOI: 10.1007/978-94-009-7801-0_3