Abstract
In this paper, we study single-machine scheduling problem when each job is considered with linear earliness and quadratic tardiness penalties with no machine idle time. Here the objective is to find the best sequence of jobs in the reasonable time. This model was studied in several researches, and some algorithms were proposed to solve it such as genetic algorithm. As the size of problem increased, such algorithms were not effective and efficient. Hence, we proposed the hybrid imperialist competitive algorithm. The proposed algorithm is based upon the imperialist competitive algorithm and genetic algorithm concepts. This algorithm was tested in problems with different sizes. The results denoted that the hybrid algorithm can solve different size of problem in reasonable time. This procedure showed its efficiency in medium- and large-sized problems as compared with other available methods.
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
Abdul-Razaq TS, Potts CN (1988) Dynamic programming state–space relaxation for single machine scheduling. J Oper Res Soc 39:141–152
Atashpaz E, Hashemzadeh G, Rajabioun F (2008) Colonial competition algorithm: a novel approach for PID controller design in MIMO distillation column process. Int J Intell Comput Cybern 1(3):337–355
Atashpaz E, Lucas C (2007) Imperialist competitive algorithm: an algorithm for optimization inspired by imperialist competitive. IEEE Congress on Evolutionary Computation 4661–4667
Bagchi U, Sullivan RS, Chang YL (1986) Minimizing mean absolute deviation of completion times about a common due date. Nav Res Logist Q 33:227–240
Baker KR (1974) Introduction to sequencing and scheduling. Wiley, New York
Baker KR, Scudder GD (1990) Sequencing with earliness and tardiness penalties: a review. Oper Res 38:22–36
Du J, Leung JY (1990) Minimizing total tardiness on one machine is NP-hard. Math Oper Res 15:483–495
Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading
Hall NG (1986) Single and multiple-processor models for minimizing completion time variance. Nav Res Logist Q 33:49–54
Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, re-issued by MIT Press (1992)
Holland JH (1962) Outline for a logical theory of adaptive systems. J Assoc Comput Mach 9(3):297–314
Kanet JJ (1981) Minimizing the average deviation of job completion times about a common due date. Nav Res Logist Q 28:643–651
Korman K (1994) A pressing matter. Video 46–50
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 Southern California
Ow PS, Morton TE (1988) Filtered beam search in scheduling. Int J Prod Res 26:35–62
Ow PS, Morton TE (1989) The single machine early/tardy problem. Manag Sci 35:177–191
Reeves CR (1997) Genetic algorithms for the operations researcher. INFORMS J Comput 9:231–250
Reeves C (2003) Genetic algorithms. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics. Kluwer, Dordrecht, pp 55–82
Schaller J (2004) Single machine scheduling with early and quadratic tardy penalties. Comput Ind Eng 46:511–532
Sidney JB (1977) Optimal single machine scheduling with earliness and tardiness penalties. Oper Res 25:62–69
Valente JMS (2008) An exact approach for the single machine scheduling problem with linear early and quadratic tardy penalties. Asia Pac J Oper Res 25:169–186
Valente JMS (2008) Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time. Comput Ind Eng 55:663–675
Valente JMS (2009) Beam search heuristics for the single machine scheduling problem with linear earliness and quadratic tardiness costs. Asia Pac J Oper Res 26:319–339
Valente JMS (2007) Heuristics for the single machine scheduling problem with early and quadratic tardy penalties. Eur J Ind Eng 1:431–448
Valente JMS, Goncalves JF (2009) A genetic algorithm approach for the single machine scheduling problem with linear earliness and quadratic tardiness penalties. Comput Oper Res 36:2707–2715
Wagner BJ, Davis DJ, Kher H (2002) The production of several items in a single facility with linearly changing demand rates. Decis Sci 33:317–346
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Banisadr, A.H., Zandieh, M. & Mahdavi, I. A hybrid imperialist competitive algorithm for single-machine scheduling problem with linear earliness and quadratic tardiness penalties. Int J Adv Manuf Technol 65, 981–989 (2013). https://doi.org/10.1007/s00170-012-4233-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-012-4233-x