article

Parallel GRASP with path-relinking for job shop scheduling

Authors:

M. G. C. ResendeAuthors Info & Claims

Parallel Computing, Volume 29, Issue 4

Pages 393 - 430

https://doi.org/10.1016/S0167-8191(03)00014-0

Published: 01 April 2003 Publication History

Abstract

In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines under certain constraints, such that the maximum completion time of the jobs is minimized. In this paper, we describe a parallel greedy randomized adaptive search procedure (GRASP) with path-relinking for the JSP. Independent and cooperative parallelization strategies are described and implemented. Computational experience on a large set of standard test problems indicates that the parallel GRASP with path-relinking finds good-quality approximate solutions of the JSP.

References

[1]

{1} E.D. Taillard, Parallel taboo search techniques for the job shop scheduling problem, ORSA Journal on Computing 6 (1994) 108-117.

[2]

{2} J.K. Lenstra, A.H.G. Rinnooy Kan, Computational complexity of discrete optimization problems, Annals of Discrete Mathematics 4 (1979) 121-140.

[3]

{3} D. Applegate, W. Cook, A computational study of the job-shop scheduling problem, ORSA Journal on Computing 3 (1991) 149-156.

[4]

{4} P. Brucker, B. Jurisch, B. Sievers, A branch and bound algorithm for the job-shop scheduling problem, Discrete Applied Mathematics 49 (1994) 105-127.

Digital Library

[5]

{5} J. Carlier, E. Pinson, An algorithm for solving the job-shop problem, Management Science 35 (1989) 164-176.

Digital Library

[6]

{6} J. Carlier, E. Pinson, A practical use of Jackson's preemptive schedule for solving the job-shop problem, Annals of Operations Research 26 (1990) 269-287.

Digital Library

[7]

{7} B. Giffler, G.L. Thompson, Algorithms for solving production scheduling problems, Operations Research 8 (1960) 487-503.

Digital Library

[8]

{8} H. Fisher, G.L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, in: J.F. Muth, G.L. Thompson (Eds.), Industrial Scheduling, Prentice Hall, Englewood Cliffs, NJ, 1963, pp. 225-251.

[9]

{9} E. Pinson, The job shop scheduling problem: a concise survey and some recent developments, in: P. Chrétienne, E. Coffman Jr., J. Lenstra, Z. Liu (Eds.), Scheduling theory and Its Application, John Wiley and Sons, 1995, pp. 277-293.

[10]

{10} R.J.M. Vaessens, E.H.L. Aarts, J.K. Lenstra, Job shop scheduling by local search, INFORMS Journal on Computing 8 (1996) 302-317.

Digital Library

[11]

{11} S. French, Sequencing and Scheduling: An Introduction to the Mathematics of the Job-shop, Horwood, 1982.

[12]

{12} J. Adams, E. Balas, D. Zawack, The shifting bottleneck procedure for job shop scheduling, Management Science 34 (1988) 391-401.

Digital Library

[13]

{13} H. Lourenço, Local optimization and the job-shop scheduling problem, European Journal of Operational Research 83 (1995) 347-364.

[14]

{14} H. Lourenço, M. Zwijnenburg, Combining the large-step optimization with tabu-search: application to the job-shop scheduling problem, in: I. Osman, J. Kelly (Eds.), Meta-Heuristics: Theory and Apllications, Kluwer Academic Publishers, 1996, pp. 219-236.

[15]

{15} P.J.M. Van Laarhoven, E.H.L. Aarts, J.K. Lenstra, Job shop scheduling by simulated annealing, Operations Research 40 (1992) 113-125.

Digital Library

[16]

{16} E. Nowicki, C. Smutnicki, A fast taboo search algorithm for the job shop problem, Management Science 42 (1996) 797-813.

Digital Library

[17]

{17} L. Davis, Job shop scheduling with genetic algorithms, in: Proceedings of the First International Conference on Genetic Algorithms and their Applications, Morgan Kaufmann, 1985, pp. 136-140.

Digital Library

[18]

{18} S. Binato, W. Hery, D. Loewenstern, M. Resende, A GRASP for job shop scheduling, in: C. Ribeiro, P. Hansen (Eds.), Essays and Surveys on Metaheuristics, Kluwer Academic Publishers, 2001, pp. 59-79.

[19]

{19} A.S. Jain, 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, Dundee, Scotland, 1998.

[20]

{20} T. Feo, M. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters 8 (1989) 67-71.

Digital Library

[21]

{21} T. Feo, M. Resende, Greedy randomized adaptive search procedures, Journal of Global Optimization 6 (1995) 109-133.

[22]

{22} P. Festa, M. Resende, GRASP: an annotated bibliography, in: C. Ribeiro, P. Hansen (Eds.), Essays and Surveys on Metaheuristics, Kluwer Academic Publishers, 2001, pp. 325-367.

[23]

{23} M. Resende, C. Ribeiro, Greedy randomized adaptive search procedures, in: F. Glover, G. Kochenberger (Eds.), Handbook of Metaheuristics, Kluwer Academic Publishers, 2002, pp. 219-249.

[24]

{24} B. Roy, B. Sussmann, Les problèmes d'ordonnancement avec contraintes disjonctives, 1964.

[25]

{25} F. Glover, Tabu search and adaptive memory programing--advances, applications and challenges, in: R. Barr, R. Helgason, J. Kennington (Eds.), Interfaces in Computer Science and Operations Research, Kluwer, 1996, pp. 1-75.

[26]

{26} F. Glover, Multi-start and strategic oscillation methods--principles to exploit adaptive memory, in: M. Laguna, J. Gonzáles-Velarde (Eds.), Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, Kluwer, 2000, pp. 1-24.

[27]

{27} F. Glover, M. Laguna, Tabu Search, Kluwer Academic Publishers, 1997.

Digital Library

[28]

{28} F. Glover, M. Laguna, R. Martí, Fundamentals of scatter search and path relinking, Control and Cybernetics 39 (2000) 653-684.

[29]

{29} M. Laguna, R. Martí, GRASP and path relinking for 2-layer straight line crossing minimization, INFORMS Journal on Computing 11 (1999) 44-52.

Digital Library

[30]

{30} R. Aiex, M. Resende, P. Pardalos, G. Toraldo, GRASP with path-relinking for the three-index assignment problem, Technical Report, AT&T Labs-Research, 2000.

[31]

{31} S. Canuto, M. Resende, C. Ribeiro, Local search with perturbations for the prize-collecting Steiner tree problem in graphs, Networks 38 (2001) 50-58.

[32]

{32} M. Resende, C. Ribeiro, A grasp with path-relinking for permanent virtual circuit routing, Technical Report, AT&T Labs Research, 2001.

[33]

{33} C. Ribeiro, E. Uchoa, R. Werneck, A hybrid GRASP with perturbations for the Steiner problem in graphs, Technical Report, Computer Science Department, Catholic University of Rio de Janeiro, 2001.

[34]

{34} C. Fleurent, F. Glover, Improved constructive multistart strategies for the quadratic assignment problem using adaptive memory, INFORMS Journal on Computing 11 (1999) 198-204.

Digital Library

[35]

{35} M. Verhoeven, E. Aarts, Parallel local search, Journal of Heuristics 1 (1995) 43-66.

[36]

{36} M. Snir, S. Otto, S. Huss-Lederman, D. Walker, J. Dongarra, The MPI Core, MPI--The Complete Reference, vol. 1, The MIT Press, 1998.

Digital Library

[37]

{37} J.E. Beasley, OR-Library: distributing test problems by electronic mail, Journal of the Operational Research Society 41 (1990) 1069-1072.

[38]

{38} R. Aiex, M. Resende, C. Ribeiro, Probability distribution of solution time in GRASP: an experimental investigation, Technical Report, AT&T Labs Research, Florham Park, NJ 07733, 2000.

[39]

{39} J.M. Chambers, W.S. Cleveland, B. Kleiner, P.A. Tukey, Graphical Methods for Data Analysis, Chapman & Hall, 1983.

Cited By

Castello Rosa APereira F(2024)An intensification approach based on fitness landscape characteristics for job shop scheduling problemJournal of Combinatorial Optimization10.1007/s10878-024-01176-047:5Online publication date: 18-May-2024
https://dl.acm.org/doi/10.1007/s10878-024-01176-0
Almeida ALima JCarvalho M(2022)Systematic Literature Review on Parallel Trajectory-based MetaheuristicsACM Computing Surveys10.1145/355048455:8(1-34)Online publication date: 23-Dec-2022
https://dl.acm.org/doi/10.1145/3550484
Mahmud SChakrabortty RAbbasi ARyan M(2022)Switching strategy-based hybrid evolutionary algorithms for job shop scheduling problemsJournal of Intelligent Manufacturing10.1007/s10845-022-01940-133:7(1939-1966)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10845-022-01940-1
Show More Cited By

Index Terms

Parallel GRASP with path-relinking for job shop scheduling
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
      1. Approximation
    2. Nonlinear equations
2. Theory of computation

Recommendations

A GRASP with Path Relinking for the Single Machine Total Weighted Tardiness Problem
HIS '08: Proceedings of the 2008 8th International Conference on Hybrid Intelligent Systems

This study considers a single machine scheduling problem with the objective of minimizing the total weighted tardiness of the jobs. This problem is one of the most famous problems in single machine scheduling theory and it is NP-hard. In this paper, we ...
A Hyper-Heuristic Using GRASP with Path-Relinking: A Case Study of the Nurse Rostering Problem

The goal of hyper-heuristics is to design and choose heuristics to solve complex problems. The primary motivation behind the hyper-heuristics is to generalize the solving ability of the heuristics. In this paper, the authors propose a Hyper-heuristic ...
A hybrid data mining GRASP with path-relinking

The exploration of hybrid metaheuristics-combination of metaheuristics with concepts and processes from other research areas-has been an important trend in combinatorial optimization research. An instance of this study is the hybrid version of the GRASP ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 April 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Castello Rosa APereira F(2024)An intensification approach based on fitness landscape characteristics for job shop scheduling problemJournal of Combinatorial Optimization10.1007/s10878-024-01176-047:5Online publication date: 18-May-2024
https://dl.acm.org/doi/10.1007/s10878-024-01176-0
Almeida ALima JCarvalho M(2022)Systematic Literature Review on Parallel Trajectory-based MetaheuristicsACM Computing Surveys10.1145/355048455:8(1-34)Online publication date: 23-Dec-2022
https://dl.acm.org/doi/10.1145/3550484
Mahmud SChakrabortty RAbbasi ARyan M(2022)Switching strategy-based hybrid evolutionary algorithms for job shop scheduling problemsJournal of Intelligent Manufacturing10.1007/s10845-022-01940-133:7(1939-1966)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s10845-022-01940-1
Amirghasemi M(2022)An effective parallel evolutionary metaheuristic with its application to three optimization problemsApplied Intelligence10.1007/s10489-022-03599-w53:5(5887-5909)Online publication date: 5-Jul-2022
https://dl.acm.org/doi/10.1007/s10489-022-03599-w
Nogueira BBarboza E(2021)A FPGA-based accelerated architecture for the Continuous GRASPComputing10.1007/s00607-020-00850-5103:7(1333-1352)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s00607-020-00850-5
Yepes-Borrero JVilla FPerea FCaballero-Villalobos J(2020)GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and additional resourcesExpert Systems with Applications: An International Journal10.1016/j.eswa.2019.112959141:COnline publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1016/j.eswa.2019.112959
Toshev A(2019)Particle Swarm Optimization and Tabu Search Hybrid Algorithm for Flexible Job Shop Scheduling Problem – Analysis of Test ResultsCybernetics and Information Technologies10.2478/cait-2019-003419:4(26-44)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.2478/cait-2019-0034
Samorani MWang YWang YLv ZGlover F(2019)Clustering-driven evolutionary algorithms: an application of path relinking to the quadratic unconstrained binary optimization problemJournal of Heuristics10.1007/s10732-018-9403-z25:4-5(629-642)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10732-018-9403-z
Arruda TDias UDias Z(2018)A GRASP-Based Heuristic for the Sorting by Length-Weighted Inversions ProblemIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2015.247440015:2(352-363)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1109/TCBB.2015.2474400
Kuroda MHanada YOno K(2018)Effectiveness of Multi-step Crossover in Extrapolation Domain for Genetic Programming2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC.2018.00618(3654-3659)Online publication date: 7-Oct-2018
https://dl.acm.org/doi/10.1109/SMC.2018.00618
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents