Advanced search
Publication Cover
International Journal of Production Research Volume 41, 2003 - Issue 5
Submit an article Journal homepage
63
Views
27
CrossRef citations to date
0
Altmetric
Original Articles

Measures of subproblem criticality in decomposition algorithms for shop scheduling

H. Aytug Department of Decision and Information Sciences, Warrington College of Business, University of Florida, Gainesville, FL, 32611, USA
,
K. Kempf Intel Corporation, MS CH3-68, 5000 W. Chandler Blvd, Chandler, AZ, 85226, USA
&
R. Uzsoy Laboratory for Extended Enterprises at Purdue, School of Industrial Engineering, Purdue University, 1287 Grissom Hall, West Lafayette, IN, 47907-1287, USA
Pages 865-882 | Published online: 14 Nov 2010

  • AARTS , E. H. L. , VAN LAARHOVEN , P. J. M. , LENSTRA , J. K. and ULDER , N. L. J. 1994 . A computational study of local search algorithms for job shop scheduling . ORSA Journal on Computing , 6 : 118 – 125 .
  • ADAMS , J. , BALAS , E. and ZAWACK , D. 1988 . The shifting bottleneck procedure for job-shop scheduling . Management Science , 34 : 391 – 401 .
  • APPLEGATE , D. and COOK , W. 1991 . A computational study of job shop scheduling . ORSA Journal of Computing , 3 : 149 – 156 .
  • BALAS , E. 1969 . Machine sequencing via disjunctive graphs: an implicit enumeration approach . Operation Research , 17 : 941 – 957 .
  • BALAS , E. , LENSTRA , J. K. and VAZACOPOULOS , A. 1995 . The one machine scheduling with delayed precedence constraints . Management Science , 41 : 94 – 109 .
  • BALAS , E. and VAZACOPOULOS , A. 1998 . Guided local search with shifting bottleneck for job shop scheduling . Management Science , 44 : 262 – 275 .
  • BHASKARAN , K. and PINEDO , M. 1991 . “ Dispatching ” . In Handbook of Industrial Engineering , Edited by: Salvendy , G. New York : Wiley .
  • BRUCKER , P. , JURISCH , B. and SIEVERS , B. 1994 . A branch and bound algorithm for the job shop scheduling problem . Discrete Applied Mathematics , 49 : 102 – 127 .
  • CARLIER , J. 1982 . The one machine scheduling problem . European Journal of Operational Research , 11 : 42 – 47 .
  • CARLIER , J. and PINSON , E. 1989 . An algorithm for solving the job-shop problem . Management Science , 35 : 164 – 176 .
  • CHEN , C. C. and YIH , Y. 1996 . Identifying attributes for knowledge-based development in dynamic scheduling environments . International Journal of Production Research , 34 : 1739 – 1755 .
  • DAUZERE-PERES , S. and LASSERRE , J. B. 1993 . A modified shifting bottleneck procedure for job shop scheduling . International Journal of Production Research , 31 : 923 – 932 .
  • DEMIRKOL , E. , MEHTA , S. V. and UZSOY , R. 1997 . Computational study of shifting bottleneck procedures for shop scheduling problems . Journal of Heuristics , 3 : 111 – 137 .
  • DEMIRKOL , E. , MEHTA , S. V. and UZSOY , R. 1998 . Benchmarks for shop scheduling problems . European Journal of Operational Research , 109 : 137 – 141 .
  • DORNDORF , U. and PESCH , E. 1995 . Evolution based learning in a job shop scheduling environment . Computers and Operations Research , 22 : 25 – 40 .
  • Fox , M. S. 1990 . Constraint-guided scheduling--a short history of research at CMU . Computers in Industry , 14 : 79 – 88 .
  • Fox , M. S. and SMITH , S. F. 1984 . ISIS--A knowledge-based system for factory scheduling . Expert Systems , 1 : 25 – 49 .
  • GAREY , M. R. and JOHNSON , D. S. 1979 . Computer and Intractability: a Guide to the Theory of NP-Completeness , San Francisco, CA : W. H. Freeman .
  • HOLTSCLAW , H. H. and UZSOY , R. 1996 . Machine criticality measures and subproblem solution procedures in shifting bottleneck methods: a computational study . Journal of the Operational Research Society , 47 : 666 – 677 .
  • KEMPF , K. , RUSSELL , B. , SIDHU , S. and BARRETT , S. 1991 . Artificially intelligent schedulers in manufacturing practice . AI Magazine , 11 : 46 – 56 .
  • LAMATSCH , A. , MORLOCK , M. , NEUMANN , K. and RUBACH , T. 1988 . SCHEDULE-an expert-like system for machine scheduling . Annals of Operations Research , 16 : 425 – 438 .
  • LAWLER , E. L. , LENSTRA , J. K. , RINNOOY KAN , A. H. G. and SHMOYS , D. B. 1993 . “ Sequencing and scheduling: algorithms and complexity ” . In Handbooks in Operations Research and Management Science, Vol. 4: Logistics of Production and Inventory , Edited by: Graves , S. C. , Rinnooy Kan , A. H. G. and Zipkin , P. Vol. 4 , Amsterdam : North-Holland .
  • LUH , P. B. and HOITOMT , D. J. 1993 . Scheduling of manufacturing systems using the Lagrangian relaxation technique . IEEE Transactions on Automatic Control , 38 : 1066 – 1079 .
  • MATSUO , H. , SUH , C. J. and SULLIVAN , R. S. 1988 . A controlled search simulated annealing approach for the general job shop scheduling problem , Working Paper 03-04-88 Austin : Department of Management, Graduate School of Business, University of Texas .
  • MONTGOMERY , D. C. 1997 . Design and Analysis of Experiments , New York : Wiley .
  • NOWICKI , E. and SMUTNICKI , C. 1996 . A fast taboo search algorithm for the job shop problem . Management Science , 42 : 797 – 813 .
  • OVACIK , I. M. and UZSOY , R. 1997 . Decomposition Methods for Complex Factory Scheduling Problems , Dordrecht : Kluwer .
  • PINEDO , M. and SINGER , M. 1999 . A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop . Naval Research Logistics , 46 : 1 – 17 .
  • ROY , B. and SUSSMANN , B. 1964 . Les Problems d'Ordonnancement avec des Contraintes Disjunctives , Note DS No. 9 bis Montrouge : SEMA .
  • SADEH , N. 1991 . “ Look-ahead techniques for micro-opportunistic job shop scheduling ” . Pittsburgh, PA : School of Computer Science, Carnegie-Mellon University . PhD thesis,
  • STORER , R. H. , WU , S. D. and VACCARI , R. 1992 . New search spaces for sequencing problems with application to job shop scheduling . Management Science , 38 : 1495 – 1509 .
  • SUN , X. and NOBLE , J. S. 1999 . An approach to job shop scheduling with sequence-dependent setups . Journal of Manufacturing Systems , 18 : 416 – 430 .
  • UZSOY , R. and DEMIRKOL , E. 2000 . Decomposition methods for scheduling reentrant flow shops with sequence dependent setup times . Journal of Scheduling , 3 : 155 – 177 .
  • UZSOY , R. and WANG , C. S. 2000 . Performance of decomposition algorithms for job shop scheduling problems with bottleneck machines . International Journal of Production Research , 38 : 1271 – 1286 .
  • Yoo , W. S. and MARTIN-VEGA , L. A. 1996 . A decompositionm ethodology for schedulingsemiconductor testing operation for number of tardy job measures , Department of Computer Science, Utah State University . Research Report,

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.