مقایسه الگوریتم های ماشین-الگوریتم های یادگیری برای برنامه ریزی پویا از سیستم های تولید انعطاف پذیر

Dispatching rules are frequently used to schedule jobs in flexible manufacturing systems (FMSs) dynamically. A drawback, however, to using dispatching rules is that their performance is dependent on the state of the system, but no single rule exists that is superior to all the others for all the possible states the system might be in. This drawback would be eliminated if the best rule for each particular situation could be used. To do this, this paper presents a scheduling approach that employs machine learning. Using this latter technique, and by analysing the earlier performance of the system, ‘scheduling knowledge’ is obtained whereby the right dispatching rule at each particular moment can be determined. Three different types of machine-learning algorithms will be used and compared in the paper to obtain ‘scheduling knowledge’: inductive learning, backpropagation neural networks, and case-based reasoning (CBR). A module that generates new control attributes allowing better identification of the manufacturing system's state at any particular moment in time is also designed in order to improve the ‘scheduling knowledge’ that is obtained. Simulation results indicate that the proposed approach produces significant performance improvements over existing dispatching rules.

The different approaches available to solve the problem of flexible manufacturing system (FMS) scheduling can be divided into the following categories: the analytical, the heuristic, the simulation-based and the artificial intelligence-based approaches. The analytical approach considers an FMS scheduling problem as an optimisation model with an objective function and explicit constraints. An appropriate algorithm resolves the model (see for example, Stecke, 1983; Kimemia and Gershwin, 1985; Shanker and Tzen, 1985; Lashkari et al., 1987; Han et al., 1989; Hutchison et al., 1989; Shanker and Rajamarthandan, 1989; Wilson, 1989). In general, these problems are of a NP-complete type (Garey and Johnson, 1979), so heuristic and off-line type algorithms are usually used (Cho and Wysk, 1993; Chen and Yih, 1996). The problem is that these analytical models include simplifications that are not always valid in practice. Moreover, they are not efficient for reasonably large-scale problems.

This paper makes a comparison of three machine-learning algorithms used for dynamically scheduling jobs in a FMS. A generator module of new control attributes is also incorporated by which test error obtained with the machine-learning algorithms can be reduced, thereby improving the manufacturing system's performance. The performance of the FMS employing the scheduling system based on the nearest neighbour algorithm is compared with the other strategies, and the system proposed is shown to obtain lower mean tardiness and mean flow time values. The only exception occurs with the scheduling systems based on the nearest neighbour algorithm and on C4.5 for the criterion of mean flow time as test errors in both these algorithms are the same. Although the selected FMS is quite generic both in its configuration and in the jobs’ characteristics, and it has been widely used by other authors (see for example, Shaw et al., 1992; Kim et al., 1998; Min et al., 1998), the obtained results cannot be generalised to any type of FMS.