Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-25T21:27:18.912Z Has data issue: false hasContentIssue false
  • English
  • Français

Embedding temporal constraint propagation in machine sequencing for job shop scheduling1

Published online by Cambridge University Press:  27 February 2009

Wesley W. Chu  and
Patrick H. Ngai
Wesley W. Chu
Affiliation:
Computer Science Department, University of California, Los Angeles, CA 90024, U.S.A.
Patrick H. Ngai
Affiliation:
Computer Science Department, University of California, Los Angeles, CA 90024, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we show how a temporal constraint propagation technique can be embedded in the machine sequencing approach for solving the job shop scheduling problem. The temporal constraint propagation algorithm propagates the precedence constraints and machine interference constraints to reduce the search space generated by the machine sequencing approach. Further, by making use of the temporal nature of the job shop scheduling, efficient algorithms to propagate precedence constraints and machine interference constraints are developed. Experimental results reveal that embedding constraint propagation in the machine sequencing approach significantly reduces the computation time more than by just using the machine sequencing approach alone. Further, the proposed temporal constraint propagation algorithms provide an order of magnitude improvement on the computation time over the conventional constraint propagation algorithm.

Type
Research Article
Information
AI EDAM , Volume 7 , Issue 1 , February 1993 , pp. 37 - 52
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adams, J., Balas, E. and Zawack, D. 1988. The shifting bottleneck procedure for job shop scheduling. Management Science 34(3), 391–401.CrossRefGoogle Scholar
Adolphson, D. 1977. Single machine job sequencing with precedence constraints. Journal of Computing 6, 40–54.Google Scholar
Baker, K. 1974. Introduction to Sequencing and Scheduling. New York: John Wiley.Google Scholar
Baker, K. and Nuttle, H. 1980. Sequencing independent jobs within a single resource. Nav. Res. Logist. Q. 27, 499–510.CrossRefGoogle Scholar
Balas, E. 1969. Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Operations Research 17, 941–957.CrossRefGoogle Scholar
Bitner, J. R. and Reingold, E. M. 1976. Backtrack programming techniques. Communications of the ACM 18(11) 651–656.CrossRefGoogle Scholar
Carlier, J. and Pinson, E. 1989. An algorithm for solving the job shop problem. Management Science, 35(2) 164–176.CrossRefGoogle Scholar
Conway, R., Maxwell, W. and Miller, L. 1967. Theory of Scheduling. Reading MA: Addison-Wesley.Google Scholar
Chu, W. and Ngai, P. 1989. Constraint propagation for job shop scheduling. Proceedings of IJCAI-89 Workshop on Constraint Processing, Detroit, Michigan.Google Scholar
Erman, L., Hayes-Roth, F., Lessor, V. and Reddy, R. 1980. The Hearsay-II speech understanding system: integrating knowledge to resolve uncertainty. ACM Computer Survey, 12, 213–253.CrossRefGoogle Scholar
Florian, M., Trepant, P. and McMahon, G. 1971. An implicit enumeration algorithm for the Machine Sequencing problem. Management Science 17(12) 782–792.CrossRefGoogle Scholar
Fox, M. S. and Smith, S. F. 1984. ISIS: a knowledge-based system for factory scheduling. Expert Systems 1, 25–49.CrossRefGoogle Scholar
Fox, M. S. 1987. Constraint-directed search: a case study of job shop scheduling. Morgan Kaufmann.Google Scholar
Fox, M. S. and Sycava, K. 1990. Overview of CORTES: a constraint based approach to production planning, scheduling and control. Proceedings of the Fourth International Conference on Expert Systems in Production and Operations Management.Google Scholar
French, S. 1982. Sequencing and Scheduling: an introduction to the mathematics of job-shop. Ellis Horwood: West Sussex, 156–163.Google Scholar
Freuder, E. C. 1978. Synthesizing constraint expressions. Communications of ACM. 21(11), 958–966.CrossRefGoogle Scholar
Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman: San Francisco.Google Scholar
Giffler, B. and Thompson, G. 1960. Algorithms for solving production scheduling problems. Operations Research 12, 305–324.Google Scholar
Graham, R., Lawler, E., Lenstra, J. and Rinnooy Kan, A. 1979. Optimisation and approximation in deterministic sequencing and scheduling: a survey. Annals Discrete. Math 5, 287–326.CrossRefGoogle Scholar
Johnson, S. 1954. Optimal two- and three-stage production schedules with set-up times included, Nav. Res. Logist. Q. 1, 61–68.CrossRefGoogle Scholar
Lawler, E. 1973. Optimal sequencing of a single machine subject to precedence constraints, Management Science 19, 544–546.CrossRefGoogle Scholar
Lowerce, B. 1976. The HARPY Speech Recognition System, Ph.D. thesis, CS Dept., Carnegie-Mellon University.Google Scholar
Mackworth, A. K. 1977. Consistency in networks of relations. Artificial Intelligence 8, 99–118.CrossRefGoogle Scholar
Mackworth, A. K. and Freuder, E. C. 1985. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence 25, 65–74.CrossRefGoogle Scholar
McMahon, G. and Florian, M. 1975. On scheduling with ready times and due dates to minimize lateness. Operations Research 23, 475–482.CrossRefGoogle Scholar
Mohr, R. and Henderson, T. 1986. Arc and path consistency revisited. Artificial Intelligence 28, 225–233.CrossRefGoogle Scholar
Muth, J. and Thompson, G., eds. 1963. Industrial Scheduling. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
Ow, P. S. and Smith, S. F. 1988. Viewing scheduling as an opportunistic problem solving process. Annals of Operations Research 12, 85–108.CrossRefGoogle Scholar
Panwalker, S. and Woollam, C. 1980. Ordered flow-shop problems with no in-process waiting: further results. Journal of Operational Research Society, 31, 1039–1043.CrossRefGoogle Scholar
Rinnooy Kan, A. 1976. Machine Scheduling Problems: Classification, Complexity and Computation. The Hague: Nijhoff.Google Scholar
Sadeh, N. and Fox, M. S. 1990. Variable and value ordering heuristics for activity-based job-shop scheduling. Proceedings of the Fourth International Conference on Expert Systems in Production and Operations Management.Google Scholar
Smith, S., Ow, P., Lepape, C., McLaren, B. and Muscettola, N. 1986 a. Integrated multiple scheduling perspectives to generate detailed production plants. Proceedings of UltraTech Conference, Long Beach, CA.Google Scholar
Smith, S., Fox, M. S. and Ow, P. S. 1986 b. Constructing and maintaining detailed production plans; investigations into the development of knowledge-based factory scheduling systems. AI Magazine 7(4), 45–61.Google Scholar
Szwarc, W. 1977. Optimal two machine orderings in the 3 × n flow-shop problem. Operational Research, 225, 70–77.CrossRefGoogle Scholar
Talavage, J. and Hannam, R. 1988. Flexible Manufacturing Systems in Practice. Marcel Dekker, Inc., New York.Google Scholar
Yueh, M. 1976. On the n job, m machine sequencing problem of a flow-shop. In: Operational Research 1975 (Haley, K. B., Ed.), Amsterdam: North Holland.Google Scholar