A Single Machine Scheduling Problem with Earliness and Tardiness Penalties Using Memetic Algorithm

Abstract:

This paper considers single machine scheduling problem. The objective is to determine sum of earliness and tardiness cost has been minimized. The memetic algorithm is developed to solve this problem. To evaluate performance of memetic algorithm, the solution of propose method is compare with the optimal solution. The results show that the average percentage deviation is less than 10. Here, the computational time required by the MA is significantly less than the time required by the optimal solution method. This result is more emphasized as the problem size is getting larger.

• Periodical: Advanced Materials Research (Volumes 314-316)
• Pages: 2353-2357
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.314-316.2353
• Online since: August 2011
• Authors: Parinya Kaweegitbundit
• Keywords: Earliness, Memetic, Scheduling, Single-Machine, Tardiness

References

[1] K.R. Baker and G.D. Scudder: Sequencing with earliness and tardiness penalties, a review. Operation Research. Vol. 38 (1990), pp.22-36.

DOI: 10.1287/opre.38.1.22

[2] M.R. Garey, R.E. Tarjan and G.T. Wilfong: One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties. Mathematics of Operations Research. Vol.13 (1988), pp.330-348.

DOI: 10.1287/moor.13.2.330

[3] Q.K. Pan, M. F. Tasgetiren and Y.C. Liang: Minimizing total earliness and tardiness penalties with a common due date on a single machine using a discrete particle swarm optimization algorithm. ANTS 2006, LNCS 4150 (2006), pp.460-467.

DOI: 10.1007/11839088_46

[4] M. Mirabi: A new meta-heuristic for scheduling of single machine problem with sequence dependent setups. Australian Journal of Basic and Applied Sciences. Vol. 4(2)(2010), pp.247-256.

[5] M. Rebai and I. Kacem: Minimizing the earliness-tardiness costs on a single machin. IEEE (2008)

DOI: 10.1109/icsssm.2008.4598495

[6] D. Biskup and M. Feldmann: Benchmark for scheduling on a single machine against restrictive and unrestrictive common due dates. Computer & Operation research. Vol. 28 (2001), pp.787-801.

DOI: 10.1016/s0305-0548(00)00008-3

[7] M. Feldmann and D. Biskup: Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches. Computer & Industrial Engineering. Vol. 44 (2003), pp.307-323.

DOI: 10.1016/s0360-8352(02)00181-x

[8] C.M. Hino, D.P. Ronconi and A.B. Mendes: Minimizing earliness and tardiness penalties in single-machine problem with a common due date. European Journal of Operational Research. Vol. 160 (2005), pp.190-201.

DOI: 10.1016/j.ejor.2004.03.006

[9] W. Szwarc and S.K. Mukhopadhyay: Optimal Timing Schedules in Earliness-Tardiness Single Machine Sequencing. Naval Research Logistics. Vol. 42 (1995), pp.1109-1114.

DOI: 10.1002/1520-6750(199510)42:7<1109::aid-nav3220420709>3.0.co;2-5

[10] M. Pinedo: Pinedo, M. Scheduling: Theory, Algorithms and Systems (2nd edition).Prentice-Hall. Upper Saddle River. NJ (2002)