Research On Job Shop Scheduling Problems Based On Constraint Satisfaction Technology

For application of the Constraint Satisfaction Technology to job shop scheduling, a Constraint Satisfaction scheduling model, which treats operation start time as main variable and includes precedence and capacity constraints, is put forward.A probabilistic model of the search space, which includes operation start probability, individual demand probability of operation for machine, and aggregate demand profile, is defined that allows for the definition of more powerful look-ahead heuristics algorithm.Look-ahead heuristics algorithm, based on probabilistic model of the search space, is introduced to select critical operation from un-scheduling operation sets and to select good value from critical operation start time set. The operation with the highest contribution to the demand for the most contended resource/time interval is considered as critical operation, and that the most compatible start time of critical operation is selected firstly.The scheduler, with information model and component-based software architecture, is put forward. Experimental results of FT06 benchmark problem indicate that the scheduler not only yields significant increases in search efficiency but also achieves important reductions in search time. Base on these research result, scheduling system is implemented by ASP.net and Oracle.