Heuristic Job Shop Scheduling using Simple Multi-Attribute Rating Techniques

Kwang Cheok King

Abstract

Job shop scheduling is a highly constrained problem that changes from shop to shop. In order to obtain the optimum makespan, mean flow time or other objectives of large sized problems, a huge amount of computational time is required. Dispatching rules provides satisfactory results with reduced computational time, but no single dispatching rule perform well globally. Thus, there is a need to have a decision making tool to select the appropriate rule to apply in the ever changing job shop conditions.

This project proposed using SMART (Simple Multi-Attribute Rating Technique) to select jobs when there is a queue ofjobs awaiting service at a machine. SMART requires weights for each of the dispatching rule used in order to select the appropriate job to be processed. The author proposed two methods to select weights for SMART, first method is to obtain it from solving a portion of the actual problem and the other method is to randomly generate the weights.

The feasible area of the static lOxlO problem used has irregular contours. Thus, the chance of obtaining the best weight is very low from the two methods mentioned earlier. In order to have a high chance of obtaining a satisfactory result, the author tested a few search methods to improve the makespan. Random points in designated areas search give a reasonably good chance (61%) of obtaining a low makespan. This is because feasible area of the problem is "random" in nature.

One shortcoming of this search method is its high computational time compared to dispatching rule's computational time. Nonetheless, the usage of SMART and the search methods show that humans need not decide any weights for this decision making tool to select jobs in a queue for processing.

One area worth investigating is to reduce the search computational time. The author suggested using a portion of the actual problem during the search rather than the actual problem. The search methods are not exhaustive and many other interesting search methods can be employed to see how it performs.