Sequencing jobs on a single machine: A neural network approach

This paper presents an approach for single machine job sequencing problems that is based on artificial neural networks. A problem is classified first by one type of neural network into one of a number of categories. The categorization is based on the problem's characteristics. Then another neural network, which is specialized for a particular category, applies a previously ‘learnt’ relationship to produce a job sequence that aims to better satisfy the given objective. The learning is acquired in these networks after a training process in which the network is exposed repeatedly to a set of example problems and their solutions. The trained network thereby learns predominant relationships between given problems, and the output sequences that optimally meet the desired objective. The advantage of such an approach is that it allows what amounts to a ‘customized’ heuristic to be established for problem subsets and various objectives without having to deduce an algorithm in advance. The methodology and its implementation is described for several of the more common sequencing objectives, as well as for a hypothetical objective that minimizes a cost function exhibiting a limited exponential behaviour.