شبکه های عصبی و روش ترکیبی مبتنی بر الگوریتم ژنتیکی برای گسترش برنامه ریزی تولید کارگاهی

The expanded job-shop scheduling problem (EJSSP) is a practical production scheduling problem with processing constraints that are more restrictive and a scheduling objective that is more general than those of the standard job-shop scheduling problem (JSSP). A hybrid approach involving neural networks and genetic algorithm (GA) is presented to solve the problem in this paper. The GA is used for optimization of sequence and a neural network (NN) is used for optimization of operation start times with a fixed sequence. After detailed analysis of an expanded job shop, new types of neurons are defined to construct a constraint neural network (CNN). The neurons can represent processing restrictions and resolve constraint conflicts. CNN with a gradient search algorithm, gradient CNN in short, is applied to the optimization of operation start times with a fixed processing sequence. It is shown that CNN is a general framework representing scheduling problems and gradient CNN can work in parallel for optimization of operation start times of the expanded job shop. Combining gradient CNN with a GA for sequence optimization, a hybrid approach is put forward. The approach has been tested by a large number of simulation cases and practical applications. It has been shown that the hybrid approach is powerful for complex EJSSP.

Scheduling is an old discipline that originated and developed almost in step with operations research starting in the 1950s. Johnson's algorithm for n/2/F/Cmax and parts of the special n/3/F/Cmax problems launched the research of scheduling theory in the 1950s. A series of representative scheduling problems were studied with pure integral programming, dynamic programming and branch and bound approach in the 1960s. Some heuristic algorithms were proposed for computing these complex problems in the last period of the 1960s. The intrinsic complexity of some scheduling problems was understood and many of them were proved to be intractable in the 1970s. The effective heuristics and their effectiveness have been intensively conducted since then. It can be said that classical scheduling theory reached maturity as a branch of applied mathematics since the end of the 1970s ( Bark, 1974). On the other hand, scheduling is also a young discipline. With the development of production technology and management, many new types of practical scheduling problem are emerging constantly and need to be solved. Working emphases have been shifted to solving practical problems. New techniques emerging from the field of AI have been introduced to this discipline since the 1980s. The job-shop scheduling problem (JSSP) is a simplified version of real production scheduling problems. In this paper, a more realistic problem, namely the expanded job-shop scheduling problem (EJSSP), is studied. EJSSP considers various constraints such as job delivery due dates and resource available times in addition to those considered by the standard JSSP. In general, the research approach to production scheduling falls into the following three categories: heuristic priority rules, combinatorial optimization (Dubois, Fargier & Prade, 1995), and knowledge-based system with intelligence (Shaw, Park & Raman, 1992). Each method has its own drawbacks. Although priority rules, especially some heuristic priority rules have been applied extensively because of their simplicity and ease of implementation, the resulting scheduling results cannot be predicted beforehand. There are no systematic methods of designing heuristics for a specific scheduling task. Analytic optimization is a desired method because it is efficient. Unfortunately, there is no generally analytic optimization algorithm for intrinsically complex NP-hard combinatorial optimization problems. In the intelligent scheduling information system (ISIS), a knowledge-based scheduling system first developed by Fox (1994), the constraint propagation technique is applied to solve a practical scheduling problem. There is a long way to go before a comprehensive theory and system for scheduling is fully developed, even though ISIS arouses the enthusiasm of those studying practical production scheduling problems. Recently, much attention has been paid to applying neural networks (NNs) and genetic algorithms (GAs) to production scheduling problems. There are three existing ways of scheduling tasks using NNs. One way is to take advantage of the parallel computing ability of NNs to solve scheduling optimization problems (Jain & Meeran, 1998). This method's drawback lies in its non-availability for universal scheduling problems, because there are no systematic means of constructing a proper energy function for them. The second way should be classified within the intelligent scheduling category, in which an NN is used to acquire scheduling knowledge by dint of its learning ability (Wang, 1995). The intelligent scheduling with NNs has given elementary results, but it needs a lot of supporting sample data and is not yet applicable to practical problems. The last way is to describe production constraints and encode scheduling rules in the NN. Intrinsically, this is one kind of heuristic scheduling. Only feasible schedules can result from the network's operation (Foo and Takefuji, 1988, Chang and Jeng, 1995 and Willems and Rooda, 1994). The major problems in this approach are (1) lack of ability to acquire optimal solutions; and (2) suitability only for specific simple scheduling problems. In recent years, an interest in applying intelligent computing methods to job-shop scheduling has grown rapidly. Steinhofel, Albrecht and Wong (1999) present two simulated annealing-based algorithms for the classical JSSP where the objective is to minimize the makespan. To overcome the problem that convergence of simulated annealing does not hold in the application to job-shop scheduling, Kolonko (1999) proposed a new approach that uses a small population of SA runs in the GA framework. Moreover, an SA algorithm using three perturbation schemes, viz. pairwise exchange, insertion, and random insertion, for job-shop scheduling is put forward by Ponnambalam, Jawahar and Aravindan (1999). Meanwhile, GA is also an efficient method for JSSP. Cheng et al., 1999 and Cheng et al., 1999 summarize the representations and search strategies of GA only for standard JSSP. A hybrid approach combining GA with multi-criteria decision-making (MCDM) and constraint logic programming (CLP) is proposed by Mesghouni, Pesin, Trentesaux, Hammadi, Tahon and Borne (1999), where GA, assisted by MCDM and CLP, plays the role of optimization. Additionally, Sakawa and Mori (1999) put forward a GA algorithm for JSSP with fuzzy processing time and fuzzy due date. The approach based on genetized-knowledge GA (gkGA) of Ombuki, Nakamura and Onaga (1999) encodes knowledge of heuristics as genes of GA. Moreover, Ghedjati (1999) uses GA to solve the JSSP with unrelated parallel machines and precedence constraints, which is another kind of EJSSP and is different from the problem of this paper. In addition, Candido, Khator and Barcia (1998) present an algorithm based on GA for JSSP with multi-constraints considering sub-assembly levels, where the problem is a specific example of our considered problem. EJSSP of the paper is a special scheduling problem with no known solution techniques involving GA and NN. Job-shop scheduling can be decomposed into a constraint satisfactory part and an optimization part for a specified scheduling objective. For this, an NN and GA-based hybrid scheduling approach is proposed in this paper. First, several specific types of neuron are designed to describe these processing constraints, detecting whether constraints are satisfied and resolving the conflicts by their feedback adjustments. Constructed with these neurons, the constraint neural network (CNN) can generate a feasible solution for the EJSSP. CNN here corresponds to the constraint satisfactory part. A gradient search algorithm can be applied to guide CNN operations if an optimal solution needs to be found at a fixed sequence. For sequence optimization, a GA is employed. Through many simulation experiments and practical applications, it is shown that the approach can be used to model real production scheduling problems and to efficiently find an optimal solution. The hybrid approach is an ideal combination of the constraint analysis initiated by Erschler, Roubellat and Vemhes (1976) and the optimization scheduling method (Zhang & Yan, 1995). This paper is organized as follows. In Section 2, an expanded job shop is described. CNN, a framework for representing various constraints and resolving conflicts, is introduced in Section 3. A gradient search algorithm is introduced to the CNN in Section 4. The hybrid approach is presented based on the gradient CNN and GA in Section 5. A case study and our conclusions are presented in 6 and 7, respectively.

The hybrid approach presented in this paper is based on the original idea of combining the constraint satisfaction neural network with scheduling optimization. CNN is easy to implement owing to its object-oriented character. The computational ability of the hybrid approach is strong enough to deal with complex scheduling problems, thanks to the NN's parallel computability and the GA's searching efficiency. Many experiments have shown that this hybrid approach is extremely promising for expanded job-shop scheduling.