Abstract
In order to obtain efficiency and flexibility, assignment of machines’ layout and determination of jobs’ schedule on each machine are among the most important decisions. These decisions are interrelated and may impact each other but they are often treated separately or as a sequential decision in prior researches. In this paper, we propose a new approach to concurrently make the layout and scheduling decisions in a job shop environment. In other words, we consider an extension of the well-known job shop scheduling problem with transportation delay in which in addition to decisions made in the classic problem, the locations of machines have to be selected among possible sites. The only goal of the problem is the minimization of the makespan. A hybrid metaheuristic approach based on the scatter search algorithm is developed to tackle this problem. Using 43 randomly generated benchmark instances, the performance of the scatter search and its components are evaluated. We also applied our procedure to the classic job shop scheduling problems. Computational results show that our procedure is efficient.
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
Garey EL, Johnson DS, Sethi R (1976) The complexity of flowshop and job-shop scheduling. Math Oper Res 1:117–129
Hahn P, Grant T, Hall N (1998) A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method. Eur J Oper Res 108:629–640
Erdogan G, Tansel B (2007) A branch-and-cut algorithm for quadratic assignment problems based on linearizations. Comput Oper Res 34:1085–1106
James T, Rego C, Glover F (2009) A cooperative parallel tabu search algorithm for the quadratic assignment problem. Eur J Oper Res 195:810–826
Taillard E (1991) Robust taboo search for the quadratic assignment problem. Parallel Comput 17(4–5):443–455
Ahuja RK, Orlin JB, Tiwari A (2000) A greedy genetic algorithm for the quadratic assignment problem. Comput Oper Res 27:917–934
Misevicius A (2004) An improved hybrid genetic algorithm: new results for the quadratic assignment problem. Knowl Base Syst 17:65–73
Stutzle T (2006) Iterated local search for the quadratic assignment problem. Eur J Oper Res 174:1519–1539
Hasegawa M, Ikeguchi T, Aihara K, Itoh K (2002) A novel chaotic search for quadratic assignment problems. Eur J Oper Res 139:543–556
Carlier J, Pinson E (1989) An algorithm for solving the job-shop problem. Manag Sci 35:164–176
Brucker P, Jurisch B, Sievers B (1994) A branch-and-bound algorithm for the job-shop scheduling problem. Discret Appl Math 49(1–3):107–127
Grabowski J, Wodecki M (2005) A very fast tabu search algorithm for job shop problem. In: Rego C, Alidaee B (eds) Metaheuristic optimization via memory and evolution: tabu search and scatter search. Kluwer, Boston, pp 191–211
Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manag Sci 42(6):797–813
Nowicki E, Smutnicki C (2005) An advanced tabu search algorithm for the job shop problem. J Sched 8(2):145–159
Zhang CY, Li PG, Rao YQ, Guan ZL (2008) A very fast TS/SA algorithm for the job shop scheduling problem. Comput Oper Res 35:282–294
Van Laarhoven PJM, Aarts EHL, Lenstra JK (1992) Job shop scheduling by simulated annealing. Oper Res 40(1):113–125
Nasiri MM, Kianfar F (2011) A hybrid scatter search for the partial job shop. Int J Adv Manuf Technol 52(9):1031–1038
Rego C, Duarte R (2009) A filter-and-fan approach to the job shop scheduling problem. Eur J Oper Res 194:650–662
Udomsakdigool A, Khachitvichyanukul V (2011) Ant colony algorithm for multi-criteria job shop scheduling to minimize makespan, mean flow time and mean tardiness. Int J Manag Sci Eng Manag 6(2):117–123
Pratchayaborirak T, Kachitvichyanukul V (2011) A two-stage PSO algorithm for job shop scheduling problem. Int J Manag Sci Eng Manag 6(2):84–93
Pardalos P, Shylo O (2006) An algorithm for the job shop scheduling problem based on global equilibrium search techniques. Comput Manag Sci 3:331–348
Pardalos P, Shylo O, Vazacopoulos A (2010) Solving job shop scheduling problems utilizing the properties of backbone and “big valley”. Comput Optim Appl 47:61–76
Hurink J, Knust S (2005) Tabu search algorithms for job-shop problems with a single transport robot. Eur J Oper Res 162:99–111
Li B, Zhao ZY, Li G (2005) A dynamic scheduling method for spatial layout planning. Proceeding of the Fourth International Conference on Machine Learning and Cybernetics, Guangzhou
Wu X, Chu CH, Wang Y, Yue D (2007) Genetic algorithms for integrated cell formation with machine layout and scheduling. Comput Ind Eng 53:277–289
Pinedo ML (2008) Scheduling: theory, algorithms and systems. Springer Science
Sprecher A, Kolisch R, Drexl A (1995) Semi-active, active and non-delay schedules for the resource-constrained project scheduling problem. Eur J Oper Res 82(1):94–102
Valls V, Quintanilla MS, Ballestin F (2003) Resource-constrained project scheduling: a critical reordering heuristic. Eur J Oper Res 165(2):375–386
Kolisch R (1996) Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. Eur J Oper Res 90(2):320–333
Ranjbar M, De Reyck B, Kianfar F (2009) A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling. Eur J Oper Res 193:35–48
Laguna M, Marti R (2003) Scatter search—methodology and implementations in C. Kluwer, Boston
Li KY, Willis RJ (1992) An iterative scheduling technique for resource-constrained project scheduling. Eur J Oper Res 56:370–379
Sivanandam SN, Deepa SN (2009) Introduction to genetic algorithms. Springer
Glover F, Laguna M, Marti R (2000) Fundamentals of scatter search and path relinking. Control Cybern 39:653–684
Lawrence S (1984) Supplement to resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques. Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh
Fisher H, Thompson GL (1963) Probabilistic learning combinations of local job shop scheduling rules. In: Muth JF, Thompson GL (eds) Industrial scheduling. Prentice-Hall, Englewood Cliffs, pp 225–251
Taillard ED (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278–285
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ranjbar, M., Razavi, M.N. A hybrid metaheuristic for concurrent layout and scheduling problem in a job shop environment. Int J Adv Manuf Technol 62, 1249–1260 (2012). https://doi.org/10.1007/s00170-011-3859-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-011-3859-4