Decision-Theoretic Control of Job-Shop Scheduling

Kelvin Mark Chan Weng Wew

Abstract

The use of dispatching rules has been a popular technique in Job-Shop Scheduling. Through useful in finding reasonably good solutions in a relatively short time, these rules do not always find an optimal solution. Furthermore, there is no single universal rule that is appropriate under all shop conditions. To overcome this problem, an approach based on decision-theoretic principles was designed to improve scheduling as the shop conditions change duringt the process. The method will build a decision model based on existing job shop conditions and select the most appropriate job in a machine queue to be processed first, based on the effectiveness of candidate dispatching rules in selecting that job.

The performance of this decision-theoretic model was tested on the Muth and Thompson's 6x6 and 10x10 problems. The performance measure optimized was the minimization of makespan. We found that the decision-theoretic scheduler is advantageous to other heuristic because of its single-pass characteristic, and innate capability to handle uncertainties. It is not reig, and can weigh values to possible outcomes due to uncertainty. It is also superior to using a single dispatching rule, and can be used to perform multiple criteria scheduling.