Abstract
In this paper, we consider a single-machine job scheduling problem where the objective is to minimize the weighted sum of earliness and tardiness (E/T) penalties of jobs. This problem is consistent with the just-in-time (JIT) production. We propose partitioning of permutation into subsequences (blocks) and replacing sets of moves with its representatives, significantly decreasing the size of the searched neighborhood. Some new properties of the problem and compound moves make eliminating “bad” elements and speeding up calculations possible. These properties allow us to propose a new fast local search algorithm based on a tabu search method. Computational experiments are presented and the results show that the algorithm proposed allows us to obtain the best-known results in a short time.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Baker KR, Scudder CD (1990) Sequencing with earliness and tardiness penalties: a review. Oper Res 38:22–36
Bank J, Werner F (2001) Heuristic algorithm for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties. Math Comput Model 33:363–383
Bożejko W, Wodecki M (2005) Task realization’s optimization with earliness and tardiness penalties in distributed computation systems. AWIC 2005, LNAI 3528:69–75
Bożejko W, Grabowski J, Wodecki M (2006) Block approach-tabu search algorithm for single-machine total weighted tardiness problem. Comput Ind Eng 50:1–14
Feldmann M, Biskup D (2003) Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches. Comput Ind Eng 44:307–323
Glover F (1989) Tabu search. Part I. ORSA J Comput 1:190–206
Glover F (1990) Tabu search. Part II. ORSA J Comput 2:4–32
Gordon V, Proth JP, Chu C (2002) A survey of the state-of-art of common due date assignment and scheduling research. Eur J Oper Res 139:1–25
Grabowski J, Wodecki M (2004) A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion. Comput Oper Res 31:1891–1909
Grabowski J, Wodecki M (2005) A very fast tabu search algorithm for the job shop problem. In: Rego C, Alidaee B (ed) Adaptive memory and evolution; tabu search and scatter search. Dordrecht, Kluwer Academic Publishers
Hendel Y, Soud F (2006) Efficient neighborhood search for the one-machine earliness-tardiness scheduling problem. Eur J Oper Res 173:108–119
Hoogeveen JA, Van de Velde LS (1996) A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time. INFORMS J Comput 8:402–412
Lawler EL (1977) A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Ann Discrete Math 1:331–342
Lee CY, Choi JY (1995) A generic algorithm for job sequencing problem with distinct due dates and general early-tardy penalty weights. Comput Oper Res 22:857–869
Kanett JJ (1981) Minimizing the average deviation of job completion times about a common due date. Nav Res Logist 28:643–651
Korman K (1994) A pressing matter. Video Mag 46–50, February
Landis K (1993) Group technology and cellular manufacturing in the Westvaco Los Angeles VH department. Project report in IOM 581, School of Business, University of Souther California
Lenstra JJ, Rinnoy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann Discrete Math 1:343–362
Navaz M, Enscore Jr EE, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. OMEGA 11/1:91–95
OR Library: http://sprocket.ict.pwr.wroc.pl/~wbo/benchmarks.htm
Schaller J (2004) Single-machine scheduling with early and quadratic tardy penalties. Comput Ind Eng 46:511–532
Smith WE (1956) Various optimizers for single-stage production. Nav Res Logist Q 3:59–66
Szwarc W (1993) Adjacent ordering in single-machine scheduling with earliness and tardiness penalties. Nav Res Logist 40:229–243
T’kindt V, Billaut J-C (2002) Multicriteria scheduling: theory, models and algorithms. Springer, Berlin Heidelberg New York
Tung-I Tsai (2007) A genetic algorithm for solving the single machine earliness/tardiness problem with distinct due dates and ready times. Int J Adv Manuf Technol 32:994–1000
Wan G, Yen BPC (2002) Tabu search for single-machine scheduling with distinct due windows and weighted earliness/tardiness penalties. Eur J Oper Res 142:271–281
Valente JMS, Alves RAFS (2005) Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time. Comput Ind Eng 48(2):363–375
Yano CA, Kim YD (1991) Algorithms for a class of single-machine weighted tardiness and earliness problems. Eur J Oper Res 52:167–178
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wodecki, M. A block approach to earliness-tardiness scheduling problems. Int J Adv Manuf Technol 40, 797–807 (2009). https://doi.org/10.1007/s00170-008-1395-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-008-1395-7