Paper Titles
Study on Approach to Fuzzy Product Configuration Based on Vague Customer Requirements
p.1068
Reconfigurable Manufacturing Execution Systems Based on Model-Driven Architecture
p.1072
Research on the Problem of MC Assembly Line Balancing Based on Genetic Algorithm
p.1076
Research on Analyzing and Coding Technology of Manufacturing Information Resource Based on Granularity-Structure
p.1080
A Job Shop Scheduling Heuristic Algorithm Based on Probabilistic Model of the Search Space
p.1084
A New Software Design Method Based on Configuration Conception
p.1088
Improving Supply Chain Traceability with the Integration of Logistics Information System and RFID Technology
p.1092
A Manufacturing Supply Chain Business Model and Its Implementation in a Plastics Manufacturing Company
p.1096
STEP-NC Based Integrated CAD/CAPP/CAM/CNC System
p.1100

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

Article Preview

Abstract:

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.

You might also be interested in these eBooks
Advances in Materials Manufacturing Science and Technology II View Preview

Info:

Periodical:

Materials Science Forum (Volumes 532-533)

Pages:

1084-1087

DOI:

https://doi.org/10.4028/www.scientific.net/MSF.532-533.1084

Citation:

Cite this paper

Online since:

December 2006

Authors:

Hong An Yang, Ya Ping Xu, Shu Dong Sun, Jian Jun Yu

Keywords:

Constraint Satisfaction Problems, Job Shop Scheduling, Probabilistic Model of the Search Space, Value Ordering Heuristics, Variable Ordering Heuristics

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2006 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

References

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

Google Scholar

[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.

Google Scholar

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

Google Scholar

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

Google Scholar