Background

Current industrial practice has been mainly based on assisting experienced human schedulers with major software packages that implement distinct scheduling philosophies like manufacturing resource planning (MRP), just-in-time (JIT) production (Schonberger, 1983), and optimized production timetables (OPT), while more recently enterprise-resource planning systems (ERPs) are utilized in process industries (James, 1996).

Although production scheduling has been traditionally addressed by management science, operations research, and industrial engineering, its complexity and importance have recently concentrated the efforts of different research communities concerned with artificial intelligence (Kusiak, 1987), dynamic programming, queuing-network theory (Jackson, 1963), systems simulation, large-scale systems, control theory, and other branches of engineering and computer science (Gupta, Evans, & Gupta, 1991; Rodammer, 1988).

In this work, we specifically focus on the deterministic job-shop scheduling. Job-shop scheduling due to its importance has been addressed by a plethora of approaches. Some of the elder techniques have been enumerative algorithms that provide exact solutions either by means of elaborate and sophisticated mathematical constructs—such as linear programming (Lawler, Lenstra, Rinnooy, & Shmoys, 1993), decomposition techniques, and Lagrangian relaxation—or by means of the branch and bound enumerative strategy, which involves search of a dynamically constructed tree that represents the solution space (Brandimarte & Villa, 1995). Limitations of the aforementioned enumeration techniques has led to suboptimal approximation methods, such as priority dispatch rules, that involve assignment of priority to each job primarily via heuristics (Panwalkar & Iskander, 1977), while recently, approaches employing fuzzy-logic techniques have emerged (Grabot & Geneste, 1994). Scheduling has been dominated by a set of innovative heuristic-approximation algorithms including the shifting-bottleneck procedure (Adams, Balas, & Zawack, 1988), tabu search (Glover, 1989), simulated annealing (VanLaarhoven, 1988), and genetic algorithms (Cheng et al., 1999). Furthermore, artificial intelligence methods have been applied ranging from neural networks (NNs) (Kim, Lee, & Agnihotri 1995; Sabuncuoglou & Gurgun, 1996) to constraint satisfaction techniques and expert systems. Recently, hybrid techniques that involve searching strategies that navigate heuristic algorithms in a problem domain away from local optima have been applied. Such techniques are genetic local search (Yamada & Nakano, 1996), and large-step optimization (Lourenco, 1995).

In this chapter, we present and systematically evaluate a novel neuroadaptive scheduling methodology (Rovithakis, Gaganis, Perrakis, & Christodoulou, 1999) by considering its application on a challenging existing industrial test case (Rovithakis, Perrakis, & Christodoulou, 2001). The examined neural network scheduler approaches the production-scheduling problem from a control-theory viewpoint (Gershwin, Hildebrant, Suri, & Mitter, 1986), in which scheduling is considered a dynamic activity. Thus, by defining release and dispatching times, setup times and maintenance as control input, and levels of inventory and machine status as system states, scheduling can be considered either as a regulation or tracking problem, where the requirements are to drive the state vector to some desired value (production requirement) or to follow some distributed over-time trajectory (Ioannou & Sun, 1995), respectively.

By taking advantage of current experience in the neuroadaptive control field (Rovithakis & Christodoulou, 1994, 1995, 1997) based on dynamic neural networks (NN), the deterministic job-shop scheduling problem has been considered a control-regulation problem, where system states (buffer levels) have to reach some prespecified values by means of control input commands. Based on a dynamic neural network model of the buffer states, derived in Rovithakis, Perrakis, and Christodoulou (1996,1997,1999), an adaptive continuous-time neural network controller has been developed. Dispatching commands are issued by means of a discretization process of the continuous-control input, which is defined as the operating frequency with which each distinct manufacturing operation must occur while the controller guarantees the uniform ultimate boundedness of the control error as well as the boundedness of all other signals in the closed loop.

Further evaluation of the neural network scheduler is pursued by applying it on real data derived from a challenging manufacturing system (Rovithakis et al., 2001). The selected test case—the mechanical workshop of a German company—constitutes a complex job shop with extremely heterogeneous part-processing times, with 18 product types that may visit 18 different machines having to be produced, thus demanding sequencing of a total of 273 jobs, that is the production of a total of 273 parts. The performance of the algorithm is compared with modified versions of the well-established conventional scheduling policies First In First Out (FIFO), Clear a Fraction (CAF), and Clear Largest Buffer (CLB). All schedulers are compared over a range of raw-material-arrival rates and their performance is evaluated by means of the observed makespan, work in process (WIP), inventory, backlogging costs, and average lead times.

Thus, the derived simulation results, revealing superb performance in issues of manufacturing-system stability, low WIP, average lead times, backlogging and inventory costs for the NN scheduler, establish the proposed scheduler's applicability on the control of nontrivial manufacturing cells.

The structure of the chapter proceeds as follows: In "Problem Formulation and the DNN Architecture," a description of the proposed NN scheduler is presented. In "Test Case: SHW Mechanical Workshop," the scheduling problem for the selected test case is defined and the conventional schedulers employed to facilitate comparisons in this study are described. In "Results," critical presentation of the derived results is provided, and we conclude in the final section.

0 0

Post a comment