The Problem of Using the Calculation of the Critical Path to Solver Instances of the Job Shop Scheduling Problem

Authors: Marco Antonio Cruz-Chávez, Juan Frausto-Solís, Fernando Ramos-Quintana

Abstract:

A procedure commonly used in Job Shop Scheduling Problem (JSSP) to evaluate the neighborhoods functions that use the non-deterministic algorithms is the calculation of the critical path in a digraph. This paper presents an experimental study of the cost of computation that exists when the calculation of the critical path in the solution for instances in which a JSSP of large size is involved. The results indicate that if the critical path is use in order to generate neighborhoods in the meta-heuristics that are used in JSSP, an elevated cost of computation exists in spite of the fact that the calculation of the critical path in any digraph is of polynomial complexity.

Keywords: Job Shop, CPM, critical path, neighborhood, meta-heuristic.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084348

References:

[1] Garey, M.R. and Johnson, D.S.: Computers and Intractability: A Guide of the Theory of NP-Completeness, W.H. Freeman and Co, New York, 1979.
[2] Schutten, J.M.J. Practical job shop scheduling, Annals of Operations Research, 83, 161-177, 1998.
[3] Conway, R.W., Maxwell, W.L. and Miller, L.W.: Theory of Scheduling. Addison-Wesley, Reading, Massachusetts 1967.
[4] Crawford, J.M. and Baker, A.B.: Experimental Results on the Application of Satisfiability Algorithms to Scheduling Problems, in Proc. of the 12th National Conf. on Artificial Intelligence, Austin, TX, 1092-1098, 1994.
[5] Frausto-Solís J. and Cruz-Chavez, M.A., A Reduced Codification for the Logical Representation of Job Shop Scheduling Problems, Lecture Notes in Computer Science, Springer-Verlag, ISSN: 0302-9743, Vol. 3046, 553 - 562 pp, May 14-17, 2004.
[6] Aarts E.H.L., Vaessens R.J.M. and Lenstra J.K., Job shop scheduling by local search. Memorandum COSOR 94-05, Eindhoven University of Technology, Department of Mathematics and Computing Science, P.O.Box 513, 5600 MB Eindhoven, 1994.
[7] Der, U. and Steinhöfel K., A Parallel Implementation of Job Shop Scheduling Heuristics In S├©revik, T., Manne, F., Moe, R., Gebremedhin, A.H. (eds.), Proc. 5th International Workshop on Applied Parallel Computing, Springer-Verlag (LNCS 1947), pp. 215 - 222, 2001.
[8] Steinhöfel, K., Albrecht, A., Wong C.K. An Experimental Analysis of Local Minima to Improve Neighborhood Search Computers & Operations Research, 30(14):2157-2173, 2003.
[9] Taillard. E., Parallel tabu search technique for the job shop scheduling problem. ORSA Journal of Computing, (6):108-117, 1994.
[10] Yamada, T., Rosen B.E. and Nakano, R., A Simulated Annealing approach to job shop scheduling using critical block transition operators. In IEEE int. Conf. on Neural Networks (Orlando, Florida.) pp 4687-4692, 1994.
[11] Yamada, T., and Nakano, R., A Fusion Crossover and Local Search, Proceedings of the IEEE International Conference on Industrial Technology, 0-7803-3104-4, 1996.
[12] Cruz-Chavez, M.A., and Frausto-Solís, J., Simulated Annealing with Restart to Job Shop Scheduling Problem Using Upper Bounds, Lecture Notes in Computer Science, Springer-Verlag, ISSN: 0302-9743, Vol. 3070, 860 - 865 pp, June 7-11, 2004.
[13] Laarhoven, V., Aarts E.H., and Lenstra, J.K., Job Shop Scheduling by Simulated Annealing, Operational Research 40(1), 113-125. 1992.
[14] Yildiz, H., Simulated Annealing & Applications to Scheduling Problems, Department of Industrial Engineering, Bilkent University, TR-06533, [email protected], 2000.
[15] Wang, T. Y., and Wu, K. B., An Efficient Configuration Generation Mechanism to Solve Job Shop Scheduling Problems by the Simulated Annealing Algorithm, International Journal of Systems Science, Vol. 30, No. 5, 527-532, 1999.
[16] Kelley, J .E., Critical Path Planning and Scheduling Mathematical Basis, Operations Research, 9, 296 -320, 1961.
[17] Hiller, F. S. and Lieberman, G. J., Introduction to Operations Research, ISBN: 0-07-113989-3, International Editions, 1995.
[18] J. E. Beasley. OR-Library: Distributing test problems by electronic mail. Journal of the Operational Research Society, Vol. 41. No. 11, 1069-1072, 1990, last update 2003.
[19] Chanas, S. and Zielinski, P., The Computational Complexity of the Critical Problems in a Network with Interval Activity Times, European Journal of Operational Research 136, 541-550, 2002.
[20] Adams, J., Balas E., and Zawack, D., The Shifting Bottleneck Procedure for job shop scheduling, Management Science Vol. 34, No 3, 1988.