Abstract
The genetic algorithm (GA) is a heuristics, and commonly used to solve combinational problems. It has been proven to have high effectiveness and efficiency in many application areas. However, a successful GA application requires adapting the algorithm to the characteristics of a problem. In the past decades, various articles on single machine earliness and tardiness (SET) problem using a heuristic approaching have been published. Yet, there are few research addressing the area of the SET problem with distinct due dates and ready times for jobs. In this paper, a designed GA, modified optimal timing procedure, which starts the searching with a feasible solution obtained by applying the EXP-ET rule developed by Ow and Morton is developed for the SET problem. Computational results in the provided experiment show that the designed GA improves the SET solution in both quality and efficiency.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Baker KR, Scudder GD (1990) Sequencing with earliness and tardiness penalties: a review. Oper Res 38:22–36
Ow P, Morton T (1989) The single machine early-tardy problem. Manage Sci 35:177–191
Abdul-Razaq T, Potts C (1988) Dynamic programming state-space relaxation for single-machine scheduling. J Oper Res Soc 39:141–152
Liaw CF (1999) A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem. Comput Oper Res 26:679–693
Yano CA, Kim YD (1991) Algorithms for a class of single machine weighted tardiness and earliness problems. Eur J Oper Res 52:167–178
Lee CY, Choi JY (1995) A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights. Comput Oper Res 22:857–869
Mazzini R, Armentano VA (2001) A heuristic for single machine scheduling with early and tardy costs. Eur J Oper Res 128:129–146
Wan G, Yen BP-C (2002) Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties. Eur J Oper Res 142:271–281
Garey MR, Tarjan RE, Wilfong GT (1988) One-processor scheduling with symmetric earliness and tardiness penalties. Math Oper Res 13:330–348
Vepsalainen A, Morton TE (1987) Priority rules for jobshops with weighted tardiness costs. Manage Sci 33:1035–1047
Holland JH (1975) Adaptation in natural and artificial systems. The University of Michigan Press, Ann Arbor, MI
Goldberg DE (1989) Genetic algorithms in search, optimization & machine learning. Addison-Wesley, Boston
Li Y, Ip WH, Wang DW (1998) Genetic algorithm approach to earliness and tardiness production scheduling and planning problem. Int J Prod Econ 54:65–76
Davis L (1991) Handbook of genetic algorithms. Van Nostrand, Princeton
Chang PC (1999) A branch and bound approach for single machine scheduling with earliness and tardiness penalties. Comput Math Appl 37:133–144
Potts CN, Wassenhove LNV (1982) A decomposition algorithm for the single machine total tardiness problem. Oper Res Lett 1:177–181
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tsai, TI. A genetic algorithm for solving the single machine earliness/tardiness problem with distinct due dates and ready times. Int J Adv Manuf Technol 31, 994–1000 (2007). https://doi.org/10.1007/s00170-005-0261-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-005-0261-0