APPLICATION OF ARTIFICIAL INTELLIGENCE METHODOLOGY IN JOB SHOP SCHEDULING : A NEURAL NETWORK APPROACH

Abstract

Dynamic job shop scheduling is a typical problem belonging to the NP Complete domain. The large number of possibilities in which job operations can be sequenced do not allow traditional mathematical analysis to provide satisfactory answers for a job shop of realistic scale. Most attempts at dealing with the problem focus on the use of dispatch rules. These rules assign jobs to resources by prioritising them with a scheduling factor such as processing time required of the current resource. date due, slack or work remaining of the jobs in the queue for a resource. This research investigates the use of a neural network to learn about the relative contributions of some of these scheduling factors. The neural network is trained to recognise the competitive or cooperative roles of these factors as they contribute positively or negatively, depending on the circumstances, to the current scheduling objective. The factors taken into account are desired performance criteria, arrival rate of jobs into the shop, amount of work at the next resource of jobs in the queue. processing time required of current resource. date due of jobs, work remaining and dynamic slack as shop operations are in progress. The research investigation is performed with a simulated job shop where the shop specifications, job characteristics and simulation run characteristics are derived from surveying past research into the influence of these features on scheduling performance. The research investigation consists of three phases. In phase one, dispatch rules are used to identify the individual contributions of scheduling factors through their relative performance. The results are used in phase two to train a modified multi-layer neural network using the backpropagation generalised delta rule as the learning rule. In the final phase, the trained network is used for the dynamic scheduling as it monitors continuously the state of the shop and the status of work in progress. It is applied to the controlled job shop environment used in phase one as well as a dynamic environment with varying job arrival rates. Comparison is made with the performance of the dispatch rules corresponding to the scheduling factors to determine the effectiveness of the scheduling system. The experiment shows that the neural network scheduling system is able on average to perform better than the best dispatch rules across different criteria and arrival rates. It is also able to give better results than a simple expert system derived from the results of phase one to select the best dispatch rule under different job arrival rates and scheduling criteria. This research represents an effort in the use of neural networks to learn and monitor the state of a job shop for dynamic scheduling. Further work can be done to assess the possibility of improving its performance by taking more factors as well as compound factors into account in the training of the network and the monitoring of the job shop.