A Job Shop Scheduling Heuristic Algorithm Based on Probabilistic Model of the Search Space


Article Preview

The job shop scheduling problem is an NP-hard problem and conveniently formulated as Constraint Satisfaction Problem (CSP). Research in CSP has produced variable and value ordering heuristics techniques that can help improve the efficiency of the basic backtrack search procedure. However, the popular variable and value ordering heuristics play poor in solving the large-scale job shop scheduling problem. In this paper, a new probabilistic model of the search space was introduced which allows to estimate the reliance of an operation on the availability of a reservation, and the degree of contention among unscheduled operations for the possession of a resource over some time interval. Based on this probabilistic model, new operation and reservation ordering heuristics were defined. new operation ordering heuristic selects the operation that relies most on the most contended resource/time interval, and new reservation ordering heuristic assigns to that operation the reservation which is expected to be compatible with the largest number of survivable job schedules. Computer simulations indicate that this new algorithm yields a optimal result of FT10 benchmark job shop scheduling problem under small time cost.



Materials Science Forum (Volumes 532-533)

Edited by:

Chengyu Jiang, Geng Liu, Dinghua Zhang and Xipeng Xu




H. A. Yang et al., "A Job Shop Scheduling Heuristic Algorithm Based on Probabilistic Model of the Search Space", Materials Science Forum, Vols. 532-533, pp. 1084-1087, 2006

Online since:

December 2006




[1] S.F. Mark: Constraint-Directed Search: A Case Study of Job-Shop Scheduling (PhD Thesis, Department of Computer Science, Carnegie-Mellon University, 1983).

[2] S. Norman and S.F. Mark: Proceedings of the Fourth International Conference on Expert Systems in Production and Operations Management, Hilton Head Island, S.C., (1990), pp.134-144.

[3] R. Dechter and J. Pearl: Artificial Intelligence, Vol. 34 (1988) No. 1, pp.1-38.

[4] T. Yamada and R. Nakano: Meta-Heuristics: Theory and Application (Kluwer Academic Publishers, Hingha, Ma 1996).