Abstract
This paper considers a single machine scheduling problem, with the objective of minimizing a linear combination of total tardiness and waiting time variance in which the idle time is not allowed. Minimizing total tardiness is always regarded as one of the most significant performance criteria in practical systems to avoid penalty costs of tardiness, and waiting time variance is an important criterion in establishing quality of service (QoS) in many systems. Each of these criteria is known to be non-deterministic polynomial-time hard (NP-hard); therefore, the linear combination of them is NP-hard too. For this problem, we developed a genetic algorithm (GA) by applying its general structure that further improves the initial population, utilizing some of heuristic algorithms. The GA is shown experimentally to perform well by testing on various instances.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Omar MK, Teo SC (2006) Minimizing the sum of earliness/tardiness in identical parallel machines schedule with incompatible job families: an improved MIP approach. Appl Math Comput 181(2):1008–1017
Holsenback JE, Russell RM (1992) A heuristic algorithm for sequencing on one machine to minimize total tardiness. J Oper Res Soc 43(1):53–62
Morton TE, Rachamadugu RM, Vepsalainen A (1984) Accurate myopic heuristics for tardiness scheduling. GSIA Working Paper, Carnegie-Mellon University, Pittsburgh, PA.
Yoon SH, Lee IS (2011) New constructive heuristics for the total weighted tardiness problem. J Oper Res Soc 62(1):232–237
Panneerselvam R (2006) Simple heuristic to minimize total tardiness in a single machine scheduling problem. Int J Adv Manuf Technol 30(7):722–726
Merten AG, Muller ME (1972) Variance minimization in single machine sequencing problems. Manag Sci 18(9):518–528
Ye N, Li X, Farley T, Xu X (2007) Job scheduling methods for reducing waiting time variance. Comput Oper Res 34(10):3069–3083
Eilon S, Chowdhury IG (1977) Minimising waiting time variance in the single machine problem. Manag Sci 23(6):567–575
Koksalan M, Azizoglu M, Kondakci SK (1998) Minimizing flowtime and maximum earliness on a single machine. IIE Trans 30(2):192–200
Jolai F, Rabbani M, Amalnick S, Dabaghi A, Dehghan M, Parast MY (2007) Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs. Appl Math Comput 194(2):552–560
Köksalan M, Burak Keha A (2003) Using genetic algorithms for single-machine bicriteria scheduling problems. Eur J Oper Res 145(3):543–556
M’Hallah R (2007) Minimizing total earliness and tardiness on a single machine using a hybrid heuristic. Comput Oper Res 34(10):3126–3142
Bagchi U (1989) Simultaneous minimization of mean and variation of flow time and waiting time in single machine systems. Oper Res 37(1):118–125
Molaee E, Moslehi G, Reisi M (2010) Minimizing maximum earliness and number of tardy jobs in the single machine scheduling problem. Comput Math Appl 60(11):2909–2919
Han H (2005) Multicriteria scheduling. Eur J Oper Res 167(3):592–623
Du J, Leung JYT (1990) Minimizing total tardiness on one machine is NP-hard. Math Oper Res 15(3):483–495
Wieslaw K (1993) Completion time variance minimization on a single machine is difficult. Oper Res Lett 14(1):49–59
Hamilton E (1969) One-machine sequencing to minimize certain functions of job tardiness. Oper Res 17(4):701–715
Karasakal EK, Köksalan M (2000) A simulated annealing approach to bicriteria scheduling problems on a single machine. J Heuristics 6(3):311–327
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Amiri, M., Olfat, L. & Keshavarz Ghorabaee, M. Simultaneous minimization of total tardiness and waiting time variance on a single machine by genetic algorithms. Int J Adv Manuf Technol 72, 439–446 (2014). https://doi.org/10.1007/s00170-014-5686-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-014-5686-x