Paper Title:
A Job Shop Scheduling Heuristic Algorithm Based on Probabilistic Model of the Search Space
  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.

  Info
Periodical
Materials Science Forum (Volumes 532-533)
Edited by
Chengyu Jiang, Geng Liu, Dinghua Zhang and Xipeng Xu
Pages
1084-1087
DOI
10.4028/www.scientific.net/MSF.532-533.1084
Citation
H. A. Yang, Y. P. Xu, S. D. Sun, J. J. Yu, "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
Export
Price
$32.00
Share

In order to see related information, you need to Login.

In order to see related information, you need to Login.

Authors: Ying Xin Zhang, Chao Chen, Jian Mai Shi
Chapter 9: Engineering Management and Engineering Education
Abstract:The objective of this paper is to develop procedures for allocating resources to the activities of a given baseline schedule in order to...
1539
Authors: Hui Wang
Chapter 7: Computation Methods and Algorithms for Modeling, Simulation and Optimization, Data Mining and Data Processing
Abstract:Stochastic job - shop scheduling problem (SJSSP) is a kind of stochastic programming problem which transformed from job - shop scheduling...
3956