Minimizing Total Earliness and Total Tardiness on Single Machine with Release Dates

Abstract:

This paper considers the bicriteria scheduling problem of minimizing the total earliness and the total tardiness on a single machine with release dates. In view of the fact that the problem has been characterized as NP-Hard, we propose two approximation algorithms (labeled as ETA1 and ETA2) for solving the problem. The proposed algorithms were compared with the MA heuristic selected from the literature. The two criteria (the total earliness and the total tardiness) were aggregated together into a linear composite objective function (LCOF). The performances of the algorithms were evaluated based on both effectiveness and efficiency. The algorithms were tested on a set of 1200 randomly generated single machine scheduling problems. Experimental results show that both the ETA1 and ETA2 algorithms outperformed (in terms of effectiveness and efficiency) the MA heuristic under all the considered problem sizes. Also, the ETA1 algorithm outperformed the ETA2 algorithm when the number of jobs (n) ranges between 20 and 500.

• Periodical: International Journal of Engineering Research in Africa (Volume 5)
• Pages: 30-43
• DOI: https://doi.org/10.4028/www.scientific.net/JERA.5.30
• Online since: July 2011
• Authors: Elkanah Oyetunji, Ayodeji Emmanuel Oluleye
• Keywords: Approximation Algorithm, Release Dates, Scheduling, Single-Machine, Total Earliness, Total Tardiness

References

[1] S.M. Johnson, Optimal two- and three- stage production schedule with setup times included, Naval Research Logistics, 1 (1954) 61-68.

DOI: 10.1002/nav.3800010110

[2] C. L. Chen, R.L. Bulfin, Complexity of single machine, multi-criteria scheduling problems, European Journal of Operational Research, 70 (1993) 115-125.

DOI: 10.1016/0377-2217(93)90236-g

[3] M. Ehrgott, X. Grandibleux, An Annotated Bibliography of Multiobjective Combinatorial Optimization, Report in Wirtschaftsmathematik, No. 62, Fachbereich Mathematik - Universitat Kaiserslautern, (2000).

[4] S. French, Sequencing and Scheduling. Ellis Horwood Limited, Chichester, (1982).

[5] A. Nagar, J. Haddock, S. Heragu, Multiple and bicriteria scheduling: A literature survey, European Journal of Operational Research, 81 (1995) 88-104.

DOI: 10.1016/0377-2217(93)e0140-s

[6] R. Mazzini, V.A. Armentano, A heuristic for single machine scheduling with early and tardy costs, European Journal of Operational Research, 128 (2001) 129-146.

DOI: 10.1016/s0377-2217(99)00345-8

[7] H. Chen, C. Chu, J. M. Proth, A branch and bound approach for earliness-tardiness scheduling problems with different due dates, Institut National de Recherche en Informatique et en Automatique (INRIA) Research Report, (1995).

DOI: 10.1007/978-3-642-80117-4_24

[8] G . Wan, B. P.C. Yen, Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties, European Journal of Operational Research, 142 (2002) 271–281.

DOI: 10.1016/s0377-2217(01)00302-2

[9] F. Sourd, Punctuality and idleness in Just-In-Time scheduling, European Journal of Operational Research, 167 (2005) 739–751.

DOI: 10.1016/j.ejor.2004.07.018

[10] V.A. Armentano, M. F. Franca Filho, Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach, European Journal of Operational Research, 183 (2007) 100–114.

DOI: 10.1016/j.ejor.2006.09.077

[11] J. E. Schaller, J.N.D. Gupta, Single machine scheduling with family setups to minimize total earliness and tardiness, European Journal of Operational Research, 187 (2008) 1050–1068.

DOI: 10.1016/j.ejor.2006.06.061

[12] G. Wan, B. P.C. Yen, Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs, European Journal of Operational Research, 195 (2009) 89-97.

DOI: 10.1016/j.ejor.2008.01.029

[13] S.S. Panwalkar, M.L. Smith, A. Seidmann, Common due date assignment to minimize total penalty for the one machine scheduling problem, Operations Research, 30 (1982) 391-399.

DOI: 10.1287/opre.30.2.391

[14] P. Dileepan, Common due date scheduling problem with separate earliness and tardiness penalties, Computers Operations Research, 20 (1993) 179-184.

DOI: 10.1016/0305-0548(93)90073-r

[15] Z.L. Chen, Scheduling with batch setup times and earliness-tardiness penalties, European Journal of Operational Research, 96 (1997) 518-537.

DOI: 10.1016/s0377-2217(96)00096-3

[16] S. W. Lin, S. Y. Chou, K. C. Ying, A sequential exchange approach for minimizing earliness–tardiness penalties of single-machine scheduling with a common due date, European Journal of Operational Research, 177 (2007) 1294–1301.

DOI: 10.1016/j.ejor.2005.11.015

[17] G. M. Magableh, S.J. Mason, Minimizing earliness and tardiness on parallel machines with sequence-dependent setups, International Journal of Operational Research, 8 (2010) 42-61.

DOI: 10.1504/ijor.2010.033103

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

DOI: 10.1016/s0167-5060(08)70356-x