Abstract
Examination of the job-shop scheduling literature uncovers a striking trend. As methods for the deterministic job-shop problem have gradually improved over the years, they have come to rely on neighbourhoods for selecting moves that are more and more constrained. We document this phenomenon by focusing on the approach of Nowicki and Smutnicki (Management Science, 1996, 42(6), 797–813), noted for proposing and implementing the most restrictive neighbourhood in the literature. The Nowicki and Smutnicki (NS) method which exploits its neighbourhood by a tabu search strategy, is widely recognised as the most effective procedure for obtaining high quality solutions in a relatively short time. Accordingly, we analyse the contribution of the method's neighbourhood structure to its overall effectiveness. Our findings show, surprisingly, that the NS neighbourhood causes the method's choice of an initialisation procedure to have an important influence on the best solution the method is able to find. By contrast, the method's choice of a strategy to generate a critical path has a negligible influence. Empirical testing further discloses that over 99.7% of the moves chosen from this neighborhood (by the NS rules) are disimproving—regardless of the initial solution procedure or the critical path generation procedure employed. We discuss implications of these findings for developing new and more effective job-shop algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Baker, K.R. (1974). Introduction to Sequencing and Scheduling. New York: John Wiley.
Balas, E. and A. Vazacopoulos. (1998). “Guided Local Search with Shifting Bottleneck for Job-Shop Scheduling.” Management Science 44(2), 262–275.
Blazewicz, J., W. Domschke, and E. Pesch. (1996). “The Job-Shop Scheduling Problem: Conventional and New Solution Techniques.” European Journal of Operational Research 93(1), 1–33.
Chang, Y.L., T. Sueyoshi, and R.S. Sullivan. (1996). “Ranking Dispatching Rules by Data Envelopment Analysis in a Job-Shop Environment.” IIE Transactions 28(8), 631–642.
Dell'Amico, M. and M. Trubian. (1993). “Applying Tabu Search to the Job-Shop Scheduling Problem.” Annals of Operations Research 41, 231–252.
Demirkol, E., S. Mehta, and R. Uzsoy. (1998). “Benchmarks for Shop Scheduling Problems.” European Journal of Operational Research 109(1), 137–141.
Dongarra, J.J. (1998). “Performance of Various Computers Using Standard Linear Equations Software.” Technical Report CS–89–85, Computer Science Department, University of Tennessee, Knoxville, TN 37996–1301, Tennessee, USA.
Fisher, H. and G.L. Thompson. (1963). “Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules.” In J.F. Muth and G.L. Thompson (eds.), Industrial Scheduling. Englewood Cliffs, New Jersey: Prentice Hall, Ch. 15, pp. 225–251.
French, S. (1982). Sequencing and Scheduling-An Introduction to the Mathematics of the Job-Shop. New York: Ellis Horwood, John-Wiley & Sons.
Giffler, B. and G.L. Thompson. (1960). “Algorithms for Solving Production Scheduling Problems.” Operations Research 8, 487–503.
Glover, F. and M. Laguna. (1997). Tabu Search. Norwell, MA: Kluwer Academic Publishers.
Grabowski, J., E. Nowicki, and C. Smutnicki. (1988). “Block Algorithm for Scheduling Operations in a Job-Shop System.” Przeglad Statystyczny XXXV, 1, 67–80, in Polish.
Jain, A.S. (1998). “A Multi-Level Hybrid Framework for the Deterministic Job-Shop Scheduling Problem.” Ph.D. Thesis, Department of APEME, University of Dundee, Dundee, Scotland, UK, DD1 4HN.
Jain, A.S. and S. Meeran. (1999). “Deterministic Job-Shop Scheduling: Past, Present and Future.” European Journal of Operational Research 113(2), 390–434.
Kolonko, M. (1999). “Some New Results on Simulated Annealing Applied to the Job Shop Scheduling Problem.” European Journal of Operational Research 113(1), 123–136.
Lawrence, S. (1984). “Supplement to Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques.” GSIA, Carnegie-Mellon University, Pittsburgh.
Lehmann, E.L. (1975). Nonparametrics: Statistical Methods Based on Ranks. San Francisco: Holden-Day.
Lourenço, H.R.D. and M. Zwijnenburg. (1996). “Combining the Large-Step Optimization with Tabu-Search: Application to the Job-Shop Scheduling Problem.” In I.H. Osman and J.P. Kelly (eds.), Meta-heuristics: Theory and Applications. Kluwer Academic Publishers, pp. 219–236.
Matsuo, H., C.J. Suh, and R.S. Sullivan. (1988). “A Controlled Search Simulated Annealing Method for the General Job-Shop Scheduling Problem.” Working Paper #03–04–88, Graduate School of Business, The University of Texas at Austin, Austin, Texas, USA.
Mattfeld, D.C. (1996). Evolutionary Search and the Job Shop: Investigations on Genetic Algorithms for Production Scheduling. Heidelberg, Germany: Physica-Verlag.
Nowicki, E. and C. Smutnicki. (1996). “A Fast Taboo Search Algorithm for the Job-Shop Problem.” Management Science 42(6), 797–813.
Panwalkar, S.S. and W. Iskander. (1977). “A Survey of Scheduling Rules.” Operations Research 25(1), 45–61.
Sabuncuoglu, I. and M. Bayiz. (1997). “A Beam Search Based Algorithm for the Job Shop Scheduling Problem.” Research Report: IEOR-9705, Department of Industrial Engineering, Bilkent University, 06533 Ankara, Turkey.
Taillard, É. (1994). “Parallel Taboo Search Techniques for the Job-Shop Scheduling Problem.” ORSA Journal on Computing 16(2), 108–117.
Thomsen, S. (1997). “Meta-heuristics Combined with Branch & Bound.” Technical Report, Copenhagen Business School, Copenhagen, Denmark (in Danish).
Vaessens, R.J.M., E.H.L. Aarts, and J.K. Lenstra. (1996). “Job Shop Scheduling by Local Search.” INFORMS Journal on Computing 8, 302–317.
Van Laarhoven, P.J.M., E.H.L. Aarts, and J.K. Lenstra. (1988). “Job Shop Scheduling by Simulated Annealing.” Report OS-R8809, Centrum voor Wiskunde en Informatica, Amsterdam.
Van Laarhooven, P.J.M., E.H.L. Aarts, and J.K. Lenstra. (1992). “Job Shop Scheduling by Simulated Annealing.” Operations Research 40(1), 113–125.
Werner, F. and A. Winkler. (1995). “Insertion Techniques for the Heuristic Solution of the Job-Shop Problem.” Discrete Applied Mathematics 58(2), 191–211.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Jain, A.S., Rangaswamy, B. & Meeran, S. New and “Stronger” Job-Shop Neighbourhoods: A Focus on the Method of Nowicki and Smutnicki (1996). Journal of Heuristics 6, 457–480 (2000). https://doi.org/10.1023/A:1009617209268
Issue Date:
DOI: https://doi.org/10.1023/A:1009617209268