Abstract
In this paper, we describe a greedy randomized adaptive search procedure (GRASP) for the job shop scheduling problem (JSP). We incorporate to the conventional GRASP two new concepts: an intensification strategy and POP (Proximate Optimality Principle) in the construction phase. These two concepts were first proposed by Fleurent and Glover (1999) in the context of the quadratic assignment problem. Computational experience on a large set of standard test problems indicates that GRASP is a competitive algorithm for finding approximate solutions of the job shop scheduling problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. Adams, E. Balas, and D. Zawack. The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science, 34:391–401, 1988.
R.M. Aiex, M.G.C. Resende, and C.C. Ribeiro. Probability Distribution of Solution Time in GRASP: An Experimental Investigation. To appear in: Journal of Heuristics.
D. Applegate and W.Cook. A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing, 3:149–156, 1991.
J.F. Bard and T.A. Feo. Operations Sequencing in Discrete Parts Manufacturing. Management Science, 35:249–255, 1989.
J.F. Bard, T.A. Feo, and S. Holland. A GRASP for Scheduling Printed Wiring Board Assembly. IIE Transactions, 28:155–165, 1996.
J.E. Beasley. OR-Library: Distributing Test Problems by Electronic Mail. Journal of the Operational Research Society, 41:1069–1072, 1990.
J.L. Bresina. Heuristic-Biased Stochastic Sampling. In: Proceedings of the AAAI-96, pages 271–278, 1996.
P. Brucker, B. Jurisch, and B. Sievers. A Branch and Bound Algorithm for the Job-Shop Scheduling Problem. Discrete Applied Mathematics, 49:105–127, 1994.
J. Carlier and E. Pinson. An Algorithm for Solving the Job-Shop Problem. Management Science, 35:164–176, 1989.
J. Carlier and E. Pinson. A Practical Use of Jackson’s Preemptive Schedule for Solving the Job-Shop Problem. Annals of Operations Research, 26:269–287, 1990.
L. Davis. Job Shop Scheduling with Genetic Algorithms. In: Proceedings of the First International Conference on Genetic Algorithms and their Applications, pages 136–140, Morgan Kaufmann, 1985.
P. De, J.B. Ghosj, and C.E. Wells. Solving a Generalized Model for Con Due Date Assignment and Sequencing. International Journal of Production Economics, 34:179–185, 1994.
T.A. Feo, J. Bard, and S. Holland. Facility-Wide Planning and Scheduling of Printed Wiring Board Assembly. Operations Research, 43:219–230, 1995.
T.A. Feo and J.F. Bard. Flight Scheduling and Maintenance Base Planning. Management Science, 35:1415–1432, 1989.
T.A. Feo and M.G.C. Resende. A Probabilistic Heuristic for a Computationally Difficult Set Covering Problem. Operations Research Letters, 8:67–71, 1989.
T.A. Feo and M.G.C. Resende. Greedy Randomized Adaptive Search Procedures. Journal of Global Optimization, 6:109–133, 1995.
T.A. Feo, K. Sarathy, and J. McGahan. A GRASP for Single Machine Scheduling with Sequence Dependent Setup Costs and Linear Delay Penalties. Computers and Operations Research, 23:881–895, 1996.
T.A. Feo, K. Venkatraman, and J.F. Bard. A GRASP for a Difficult Single Machine Scheduling Problem. Computers and Operations Research, 18:635–643, 1991.
P. Festa and M.G.C. Resende. GRASP: An Annotated Bibliography. In: Essays and Surveys on Metaheuristics, C.C. Ribeiro and P. Hansen, editors, Kluwer, 2001 (this volume).
H. Fisher and G.L. Thompson. Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules. In: Industrial Scheduling, J.F. Muth and G.L. Thompson, editors, pages 225–251, Prentice Hall, 1963.
C. Fleurent and F. Glover. Improved Constructive Multistart Strategies for the Quadratic Assignment Problem using Adaptive Memory. INFORMS Journal on Computing, 11:198–204, 1999.
S. French. Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Horwood, 1982.
B. Giffler and G.L. Thompson. Algorithms for Solving Production Scheduling Problems. Operations Research, 8:487–503, 1960.
F. Glover and M. Laguna. Tabu Search. In: Modern Heuristic Techniques for Combinatorial Problems, C.R. Reeves, editor, pages 70–41. Blackwell, 1993.
A.S. Jain and S. Meeran. A State-of-the-Art Review of Job-Shop Scheduling Techniques. Technical report, Department of Applied Physics, Electronic and Mechanical Engineering, University of Dundee, 1998.
M. Laguna and J.L. González-Velarde. A Search Heuristic for Just-in-Time Scheduling in Parallel Machines. Journal of Intelligent Manufacturing, 2:253–260, 1991.
M. Laguna and R. Martí. GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization. INFORMS Journal on Computing, 11:44–52, 1999.
J.K. Lenstra and A.H.G. Rinnooy Kan. Computational Complexity of Discrete Optimization Problems. Annals of Discrete Mathematics, 4:121–140, 1979.
H. Ramalhinho Lourenço, J.P. Paixaão, and R. Portugal. Metaheuristics for the Bus-Driver Scheduling Problem. Technical report, Department of Economics and Management, Universitat Pompeu Fabra, Barcelona, 1998.
H.R. Lourengo. Local Optimization and the Job-Shop Scheduling Problem. European Journal of Operational Research, 83:347–364, 1995.
H.R. Lourengo and M. Zwijnenburg. Combining the Large-Step Optimization with Tabu-Search: Application to the Job-Shop Scheduling Problem. In: Meta-Heuristics: Theory and Applications, I.H. Osman and J.P. Kelly, editors, pages 219–236, Kluwer, 1996.
E. Nowicki and C. Smutnicki. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 42:797–813, 1996.
E. Pinson. The Job Shop Scheduling Problem: A Concise Survey and Some Recent Developments. In: Scheduling Theory and its Application, P. Chrétienne, E.G. Coffman Jr., J.K. Lenstra, and Z. Liu, editors, pages 277–293, Wiley, 1995.
M. Prais and C.C. Ribeiro. Reactive GRASP: An application to a Matrix Decomposition Problem in TDM A Traffic Assignment. INFORMS Journal on Computing, 12:164–176, 2000.
R.Z. Ríos-Mercado and J.F. Bard. Heuristics for the Flow Line Problem with Setup Costs. European Journal of Operational Research, pages 76–98, 1998.
R.Z. Ríos-Mercado and J.F. Bard. An Enhanced TSP-Based Heuristic for Makespan Minimization in a Flow Shop with Setup Costs. Journal of Heuristics, 5:57–74, 1999.
B. Roy and B. Sussmann. Les problèmes d’ordonnancement avec contraintes disjonctives. SEMA Note D.S., n. 9, Paris, 1964.
E.D. Taillard. Parallel Taboo Search Techniques for the Job Shop Scheduling Problem. ORSA Journal on Computing, 6:108–117, 1994.
R.J.M. Vaessens, E.H.L. Aarts, and J.K. Lenstra. Job Shop Scheduling by Local Search. INFORMS Journal on Computing, 8:302–317, 1996.
P.J.M. Van Laarhoven, E.H.L. Aarts, and J.K. Lenstra. Job Shop Scheduling by Simulated Annealing. Operations Research, 40:113–125, 1992.
J. Xu and S. Chiu. Effective Heuristic Procedure for a Field Technician Scheduling Problem. Technical report, US WEST Advanced Technologies, 1998.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer Science+Business Media New York
About this chapter
Cite this chapter
Binato, S., Hery, W.J., Loewenstern, D.M., Resende, M.G.C. (2002). A Grasp for Job Shop Scheduling. In: Essays and Surveys in Metaheuristics. Operations Research/Computer Science Interfaces Series, vol 15. Springer, Boston, MA. https://doi.org/10.1007/978-1-4615-1507-4_3
Download citation
DOI: https://doi.org/10.1007/978-1-4615-1507-4_3
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4613-5588-5
Online ISBN: 978-1-4615-1507-4
eBook Packages: Springer Book Archive