US 5,432,887 AGrant
Neural Network System and Method for Factory Floor Scheduling
Issue Date:1995-07-11
•34 Claims
•28 Drawing Sheets
Abstract
Methods are developed on a digital computer for performing work order scheduling activity in a dynamic factory floor environment, in a manner which enables scheduling heuristic knowledge from a scheduler to be encoded through an adaptive learning process, thus eliminating the need to define these rules explicitly. A sequential assignment paradigm incrementally builds up a final schedule from a partial schedule, assigning each work order to appropriate resources in turns, taking advantage of the parallel processing capability of neural networks by selecting the most appropriate resource combination (i.e. schedule generation) for each work order under simultaneous interaction of multiple scheduling constraints.
Metadata
Assignee
- Singapore Computer Systems
Inventor
- Fook C. Khaw
Application Information
Application Number:US 0319546
Filing Date:1993-03-16
Priority Date:1993-03-16
Art Unit:238
Classifications
IPC:
G06F 1518
Field of Search:
39511;22;73;26
Patent Drawings (28 sheets)
Description
Background
This invention pertains to neural network technology, and more specifically, to a novel neural network system and method for scheduling manufacturing resources in a dynamic factory floor environment. Factory floor scheduling involves building a schedule by assigning manufacturing resources (i.e. start and end times and machines) to each operation of a work order (also known as production, job, or manufacturing orders) which is subjected to a set of production constraints (e.g. resource requirements, quality standards, priority of customer, etc.). FIG. 1 shows, in block diagram form, key concepts concerning factory floor scheduling process. Referring now to FIG. 1, work orders 810 which represent demands from customers together with production constraints 850 such as machine workload and performance goals, etc. are input to drive scheduling process 800 to produce a feasible factory floor schedule 860.
FIG. 2 shows a screen of the data which work order 810 may contain. Typically these data are entered by a production planner into a database. Data related to work order 810 can then be retrieved from the database for use by scheduling process 800. An example of these related data is depicted in the example of a Part Data Screen, as shown in FIG. 3. Given part number 910 from work order 810, data relevant to part number 910, such as family group it belongs to, standard lot size, run hours, tooling required, etc., are then retrieved from the database and used in scheduling process 800 (FIG. 1). The output of scheduling process 800 is a factory floor schedule 860 which is normally represented in the form of a Gantt chart. An example of such a Gantt chart is shown in FIG. 4. It is to be understood that FIGS. 2, 3, and 4 are merely examples for purposes of illustration.
For the past three decades, numerous methods such as MRP II 830 (for example, refer to Kanet, "MRP 96: Time to Rethink Manufacturing Logistics", Production and Inventory Management journal, 2nd Quarter, 1988), and simulation 840 (for example, refer to MacFarland, "Shop Floor Scheduling and Control Using Simulation Technology," Integrated Manufacturing, May 1990) as as shown in FIG. 1 have been developed to tackle scheduling problems on the factory floor. However, most of these prior art methods are not designed for scheduling in a dynamic factory floor environment. In reality, all factory floors are dynamic. This is because there are just too many variables and factors both on the factory floor and from marketing for a production schedule to be valid for an entire day or even a single shift. For example, machine breakdown, operator and tooling availability, and changes in the demand and order requirements all contribute to scheduling and factory floor problems. Because a schedule is generated as a plan to utilize given resources, conflicts result when resource changes occur. Therefore a good factory floor scheduling system must be able to adjust the schedule to accommodate unexpected situations, changes in order requirements, and other environmental conditions. MRP II 830 systems as shown in FIG. 1 are the most popular production scheduling tools for multi-product, small lot size job shop production environment. Despite its popularity, the MRP II 830 system has not been widely used as a scheduling tool in the dynamic factory floor due to its many deficiencies.
Other approaches to dynamic factory floor scheduling tend to be too rigid and too complicated to be applicable in a reallife scheduling environment. Simulation 140 technique as shown in FIG. 1, for example, require accurate problem formulation to make a sharp distinction between constraints (which must be satisfied) and costs. A solution which achieves a very low cost but violates one or two constraints is simply not allowed. In a real-life scheduling environment, it is usually preferable to schedule work orders with the same part number together so that the number of machine setups can be reduced. But this is not an absolute constraint. It does not apply when a work order has different due date priority. These types of "soft" constraints are inherent in many scheduling environments and the optimal solution is the one which minimizes the total number violations of soft constraints.
Neural network technology is beginning to enjoy wide-spread popularity in recent years. Neural networks are mathematical models of human biological brain. They have powerful learning algorithms that allow an application system to learn from past examples. They also possess many unique and useful properties such as parallel processing, which offer a completely different computational paradigm as compared to other approaches. In the area of scheduling, several researchers have applied neural network technology to solve this type of problem. Most of these approaches typically attempt to solve scheduling problem of not more than ten work orders 810 by using an iterative improvement paradigm with a global objective function to be optimized to search for a near-optimal solution. Examples of such neural networks are simulated annealing or Gaussian machine (for example, please refer to Akiyama, et al., "The Gaussian Machine: A Stochastic Neural Network for Solving Assignment Problems," Journal of Neural Network Computing, Winter 1991). However these approaches suffer great limitation when facing real-life scheduling environment where at any time there can be as many as 300-500 existing and new work orders 810 to be scheduled.
Summary of the Invention
The present invention provides methods which are developed on a digital computer for performing work order scheduling activity in a dynamic factory floor environment. The present invention enables scheduling heuristic knowledge from a scheduler to be encoded through an adaptive learning process, thus eliminating the need to define these rules explicitly. Unlike other neural network based scheduling system, the present invention uses a sequential assignment paradigm which incrementally builds up a final schedule from a partial schedule. This is achieved by assigning each work order to appropriate resources in turn. The present invention takes advantage of the parallel processing capability of neural networks by selecting the most appropriate resource combination (i.e. schedule generation) for each work order under simultaneous interaction of multiple scheduling constraints.
One embodiment of the system of this invention includes two main subsystems and methods. The first subsystem and method is designed to allow a system designer or a knowledge engineer to model the dynamic scheduling environment and to build up a scheduling knowledge base through a neural network learning process. It includes methods to build a simulator which functions as a automatic knowledge acquisition tool, methods to build a knowledge processor for encoding scheduling knowledge, methods to build a neural network for sequencing of work orders and methods to build a neural network for assigning resources to work orders.
The second subsystem is the actual scheduling system designed for use by a planner or a scheduler. It is developed after the first subsystem has built the knowledge bases. It includes a neural network module which consists of a sequencer including a neural network previously trained and a method for sequencing of work orders, a scheduling engine including a neural network previously trained for assigning resources to work orders, a competitive neural network and method for on-line scheduling and constraints propagation of manufacturing resources, and a knowledge processor for encoding and decoding of scheduling data. In addition, a user interface module, a database module, and a reports/charts module are also provided, allowing the users to conveniently interact with the subsystem.
Brief Description of the Drawings
The present invention as defined by the claims is better understood with the text read in conjunction with the following drawings:
FIG. 1 is one embodiment of a high level block diagram showing aspects of one embodiment of a scheduling process 800 having inputs from work order 810 and constraints 850 to produce factory schedule 860.
FIG. 2 is a representative example of a Work Order Entry Screen showing data that is contained in the screen.
FIG. 3 is a representative example of Part Data Screen which can be retrieved for a given part number associated with a work order 810 of FIG. 1.
FIG. 4 is a representative example of a Gantt chart that represents a factory floor schedule 860 of FIG. 1.
FIG. 5 is a representation of the architecture of one embodiment of the present invention.
FIG. 6 shows a representative example of a neural network with learning capability.
FIG. 7 shows a high level block diagram of one embodiment of a system for implementing the method of the present invention for building operational policy knowledge base 140 and scheduling knowledge base 150 within feedforward neural network 135 and recurrent neural network 130 respectively, through a learning process.
FIG. 8 is one embodiment of an intermediate block diagram of one embodiment of steps in accordance with this invention which make up simulator 110 of FIG. 7 for generating scheduling data for training feedforward neural network 135 and recurrent neural network 130.
FIG. 9 is one embodiment of a detailed block diagram of one embodiment of creating work order model 310 of FIG. 8 showing the steps needed to define and build the work order model.
FIG. 10 is one embodiment of a detailed block diagram of one embodiment of creating scheduling model 330 of FIG. 8 showing the steps needed to define and build the scheduling model.
FIG. 11 is one embodiment of an intermediate block diagram of one embodiment of steps for running simulator 110 for generating training data sets of FIG. 8.
FIG. 12 is one embodiment of a detailed block diagram of one embodiment of running work order model 310 of FIG. 11 for generating representative work orders 810 as training data.
FIG. 13 is one embodiment of a detailed block diagram of one embodiment of work order model 310 of FIG. 11 showing the types of input and output data used by the model in the modeling phase.
FIG. 14 is one embodiment of a detailed block diagram of one embodiment running scheduling model 330 of FIG. 11 for generating representative factory floor schedules 860 as training data.
FIG. 15 is one embodiment of a detailed block diagram of one embodiment of scheduling model 330 of FIG. 13 showing the types of input and output data used by the model in the modelling phase.
FIG. 16 shows one embodiment of a detailed block diagram of one embodiment of recurrent neural network 130 of FIG. 7 showing the types of input and output data used by the network in the learning phase.
FIG. 17 shows one embodiment of a detailed block diagram of one embodiment of feedforward neural network 135 of FIG. 7 showing the types of input and output data used by the network in the learning phase.
FIG. 18 shows a high level block diagram of one embodiment of a system for implementing method of the present invention for factory floor scheduling using a scheduling engine 260 which contains a trained recurrent neural network and a competitive neural network.
FIG. 19 shows one embodiment of an intermediate block diagram of one embodiment of the steps which make up knowledge processor 120 of FIG. 11 and FIG. 18 for translating data into neural network codes and for converting neural network output into database format.
FIG. 20 shows one embodiment of an intermediate block diagram of one embodiment of the steps which make up the sequencer 240 of FIG. 18 which contians a trained feedforward neural network for ranking work orders 810 in a priority sequence.
FIG. 21 is one embodiment of a detailed block diagram of one embodiment of the trained feedforward neural network 640 of FIG. 20 showing the types of input and output data used by the network in the recall phase.
FIG. 22 is one embodiment of an intermediate block diagram of oneembodiment of the steps which make up the scheduling engine 260 of FIG. 18 for generating schedule for producing schedgle for work orders 810.
FIG. 23 is one embodiment of a detailed block diagram of one embodiment of the steps of inputting data into neural networks of FIG. 22.
FIG. 24 is one embodiment of a detailed block diagram of one embodiment of the steps of predicting possible schedules of FIG. 22 using a trained recurrent neural network 130.
FIG. 25 is one embodiment of a detailed block diagram of one embodiment of the steps of determining output which represents schedule of FIG. 22 using competitive neural network 1700.
FIG. 26 is one embodiment of a detailed block diagram of one embodiment of the steps for constraints relaxation of FIG. 24 when scheduling of a work order is unsuccessful.
FIG. 27 is one embodiment of a detailed block diagram of one embodiment of the steps of updating connection weights of FIG. 22 for propagating constraints between competitive neural network 1700 and trained recurrent neural network 130.
FIG. 28 is one embodiment of a detailed block diagram of one embodiment of trained recurrent neural network 130 and competitive network 1700, of FIG. 22 showing the types of Input and output data used by the networks in the recall phase.
Detailed Description of Preferred Embodiments
In describing the preferred embodiments of the present invention, reference will first be made to FIG. 5. FIG. 5 is a high level block diagram which shows the major elements of one embodiment of the present invention. It should be understood that FIG. 5 is only a high level representation of the overall architecture of one embodiment of the present invention, which is intended to provide a reference point by which the preferred methods of operation of the present invention can be described.
As will be discussed in greater detail below, one embodiment of the present invention utilizes three neural networks to perform two major scheduling tasks: sequencing of work orders 810 (FIG. 1) to be scheduled according to their priority index which is calculated from a user-defined operational policy, and assignment of these work orders 810 to machines and start/end dates according to a set of scheduling constraints 850. As shown in FIG. 5, neural network module 1910, which consists of the three neural networks, receives inputs 1925 in the form of work orders 810 to be scheduled and constraint data 850 from database module 220, and produces output 1915 in the form of factory floor schedule 860 to database module 220.
Database module 220 is the location in which production data is stored. A user can retrieve existing data 1945 from and can input new data 1935 to database module 220. As shown in FIG. 5, data 1965 stored in database module 220 can also be used to generate meaningful production reports and/or Gantt charts by the reports/charts module 230 which can provide a tabular or graphical representation of scheduling output, such as the graphical representation shown in FIG. 4. In addition, the user may interact with neural network module 1910 directly when human intervention is desired during a scheduling process. This is shown in FIG. 5 as bi-directional interface 1905 between user interface module 210 and neural network module 1910.
Central to the present invention is the three neural networks contained in neural network module 1910 which is implemented in two stages. The first stage involves using a feedforward neural network to build a operational policy knowledge base and using a recurrent neural network to build a scheduling knowledge base through a training or learning process. The second stage involves using the trained feedforward neural network, the trained recurrent neural network and a competitive neural network to perform the two major scheduling tasks. A competitive neural network is a variation of feedforward architecture in which lateral inhibitory connections are allowed, and in which neurons both cooperate and compete with each other in order to carry out some task. An example of such connections is shown in inhibitory connection 1888 of FIG. 6.
In order to fully appreciate the various aspects and benefits produced by the present invention, a good understanding of neural network technology is required. For this reason, the following paragraphs discuss neural network technology as applicable to neural network module 1910 of the system and method of the present invention.
Essentially a neural network is a mathematical model of the human biological brain. It is usually implemented as a computer simulation model of a network of interconnected neurons. Although hardware implementation of neural networks is now possible, neural networks used in neural network module 1910 of the present invention are preferably conveniently provided as computer simulations which are used to solve the dynamic factory floor scheduling problem.
A neural network is a hierarchical collection of neurons, each of which may consist of five equations (summation, transfer, error, output, and learning functions) to compute results. Each neuron may receive multiple input values but produces only one output value. The outputs of neurons in a lower level layer are provided as inputs to the neurons of higher layers. The highest layer produces the final outputs.
FIG. 6 shows a representative example of a preferred form of a neural network 130 suitable for use by neural network module 1910 of the present invention. It should be noted that the example shown in FIG. 6 is merely illustrative of an embodiment of neural network module 1910. As discussed below, other embodiments for neural network module 1910 can be used. The embodiment of FIG. 6 has input layer 1810, hidden layer 1820, and output layer 1830. Input layer 1810 includes a layer of input neurons 1815 which take their values from external input data 1818.
Hidden layer 1820 includes a set of neurons 1825. The outputs of input neurons 1815 of input layer 1810 are used as inputs by each neuron 1825. More than one hidden layer 1820 can be used in the neural network, in which event subsequent hidden layers take the outputs from the previous hidden layer as their inputs. Output layer 1830 has a set of neurons 1835, which take the output of neurons 1825 (of the last hidden layer when more than one hidden layer is utilized) as their input values.
For each connection between layers 1810, 1820, and 1830, an adjustable variable called weight 1828 is defined. For purpose of illustration, only four weights 1828 are shown. However, each connection between layers 1810, 1820, and 1830 has an associated weight. Weights 1828 determine how much relative effect an input value has on the output value for a neuron. When a neuron uses its own output value in a layer, the neuron is said to have a recurrent connection 1868 as shown in FIG. 6. When each neuron in a source layer connects to all neurons in the destination layer, the two layers are said to be fully connected. When each neuron in the source layer connects to the neuron in the destination layer in corresponding position, the two layers are said to be correspondingly connected. Sometimes it is desirable to connect specific neurons in different layers to enforce certain relations; this type connection is called a special connection 1878, as shown in FIG. 6.
Having discussed the basics of neural network technology, reference will now be made in detail to a presently preferred embodiment of this invention, an example of which is illustrated in the accompanying drawings.
1. Knowledqe Acquisition 105 and Simulator 110
FIG. 7 shows a high level block diagram of the major steps which are used in accordance with this invention to build operational policy knowledge base 140 and scheduling knowledge base 150, which is part of neural network module 1910 of FIG. 5. Referring now to FIG. 7, a first knowledge acquisition step 105 involves conducting a detailed study to acquire specific knowledge and to collect data on the scheduling process and its constraints in a factory floor. Typical activities in knowledge acquisition step 105 include iterative interviews with human expert schedulers, functional and information modeling, and requirements analysis.
The data to be collected however, will vary from factory to factory. This is because the scheduling problem is domain specific due to the different types of constraints faced by a factory. The main scheduling function can be quite similar though. In general, these data include scheduling configuration (such as number of machines in a work center, scheduling horizon, types of products manufactured, etc.), scheduling constraints (such as available capacity, capability of machine, customer priority, tooling required, etc.), and scheduling logic (such as scheduling rules or heuristics, and scheduling methods).
Data collected from knowledge acquisition 105 (as shown in step pointer 191 of FIG. 7) are then used by simulator 110 method to generate training data for use by recurrent neural network in method step 130. Simulator step 110 also provides an automatic knowledge acquisition tool intended to supplement the data collection effort for a scheduling environment in a factory. Simulator 110 utilizes a simulator which may be developed using any simulation languages such as SIMAN IV, a product of Systems Modeling, Inc., of Pittsburg, Pa. or any simulation software packages such as WITNESS, a product of AT&T Istel, Visual Interactive Systems, Inc. of Cleveland, Ohio or any high level programming languages such C++.
FIG. 8 shows in more detail a representative embodiment of simulator 110. As shown in FIG. 8, this embodiment is made up of eight steps. Step pointer 191 shows that the first step of this embodiment is a create a work order model step 310, which is used to generate lists of work orders 810 (FIG. 1). Although different factories may use different types of scheduling data attached to their work orders 810, they typically include similar information such as part number, family group number, order quantity, customer's need date, and earliest start date.
A more detailed example of create work order model step 310 is shown in FIG. 9 and software listing 1 of the Appendix. As shown in FIG. 9, work orders 810 and their relevant scheduling attributes such as those described above, must first be defined (step 962). This is followed by definition of flow process for creating work orders 810 (step 964). Flow process step 964 models when and how many work orders 810 should be created, what scheduling data must be included, and when these work orders should be released to the factory floor. The next step (step 966) in creating a work order model 310 is to define experimental conditions to be setup for the model. This typically includes defining scheduling parameters such as range of part numbers, defining different machine workload conditions, etc. The last step (step 968) in FIG. 9 is to verify and validate work order model 310 to ensure model accuracy. This is normally done by using statistical method to test the output data generated by the model. A specific example of the details of steps 962, 964, 966, and 968 is shown in software listing 1 of the Appendix. It should be understood however, the details required by work order model 310 differ from factory to factory. Therefore software listing 1 of the Appendix should be treated as guidelines to create such model to be used in the present invention.
Referring again to FIG. 8, the create a scheduling model step 330 creates a scheduling model whose purpose is to model the specific scheduling logic with the specific scheduling configuration of the factory concerned. FIG. 10 shows the detailed steps and software listing 2 of the Appendix is a more detailed example of creating scheduling model 330. Similar to the create a work order model 310, the first step (step 1052 in FIG. 10) in creating scheduling model 330 is to define scheduling entities and their corresponding attributes and variables (step 1054). The next step (step 1056) if to define scheduling process flow whose function is to model the scheduling logic of the specific factory's scheduling environment. Possible simulation experimental conditions (step 1060) such as initialization of starting simulation conditions, different scheduling scenarios, etc. must also be identified and defined. Finally, the resultant model must be verified and validated (step 1060) before it is used to generate data. A specific example of the details of steps 1052, 1054, 1056, 1058, and 1060 is given in software listing 2 of the Appendix. This example should be treated as guidelines to create such model for use in the present invention.
Step 340 in FIG. 8 is to design simulation experiments using work order model 310 and scheduling model 330. To ensure sufficient and representative data are collected from simulator 110 (FIG. 7) to be used for training the neural networks, a robust design method (also known as Taguchi method) for designing simulation experiments is preferably employed. It should be understood that this particular method is merely used as an example of how training data can be generated. Using the robust design method, the total number of simulation experiments required to collect the data can be greatly reduced. This can be achieved by first identifying all the control factors (simulation parameters) to be studied. Typical examples of control factors of interest are the inputs to work order model 310 and scheduling model 330 which are machine workload, operational policy, and number of shifts per day. Simulation experiments can be conducted according to the experimental conditions as setup in the design matrix. A more detailed description of robust design method is discussed in Mayer and Benjamin, "Using The Taguchi Paradigm For Manufacturing System Design Using Simulation Experiments", Computers in Industrial Engineering, Vol. 22, No. 2, pp. 195-209, 1992, which is incorporated herein by reference.
After design of simulation experiments step 340 is completed, simulation runs can be carried out as shown in step 350 in FIG. 8 and a more detailed steps is given in FIG. 11. Referring to FIG. 11, before a simulation is run, a set of simulation parameters (i.e. control factors) must first be set according to the design (step 372). Next work order model 310 is run to generate sorted list of work orders 810 (step 374). A more detailed example of running work order model 310 which has been created in step 370 (FIG. 8) is shown in FIG. 12. In this example, the arrival of work orders (step 1211 in FIG. 12) which, in a make-to-order factory floor environment, is typically modeled as Poisson processes. The work orders created are then assigned with attributes (step 1213). The assignment of attributes to work orders created are then assigned with attributes (step 1213). The assignment of attributes to work orders are of random nature as defined in the experimental condition setup (step 966 in FIG. 9). These work orders are placed in a sorting queue (step 1215) before they are sorted according to their priority index (step 1217) which will be described in detailed in the following paragraph.
The input and output of running work order model 310 is shown in FIG. 13. The inputs to work order model 310 are machine workload 1210 and user defined operational policies 1220 whereas the output is a sorted list of work orders 810. Machine workload data 1210 is defined as the arrival rate of work orders. This data can be obtained from the factory under study. An operational policy 1220 in FIG. 13, on the other hand, is a criteria for making a particular scheduling decision based on available information at the decision point. It normally consists of weights expressing the relative importance of criteria used in the scheduling decision making. Based on the factory's specifications, the created work order is then assigned with other relevant scheduling data. The priority index of the created work order is then calculated using a user-defined formula. An example of such formula is shown below:
where;
ESD.sub.i is the earliest start date of work order i;
EDD.sub.i is the earliest due date of work order i;
PR.sub.i is the priority of work order i; and
w.sub.esd, w.sub.edd, and w.sub.pr are user-defined operational policies for work order i.
Finally work order model 310 sorts all the created work orders 810 according to their priority index (step 1217 in FIG. 12).
Referring again to FIG. 11, scheduling model 330 is run (step 378) to generate schedules for work orders 810 generated. FIG. 14 shows one exemplary embodiment of run scheduling model 378, in which the scheduling model created receives the list of work orders 810 from the work order model and attempts to schedule these work orders according to the logic and configuration of the factory floor concerned. FIG. 15 shows the input and output data as applicable to scheduling model 330. As shown in FIG. 15, beside the list of work orders 810, the other input to the scheduling model is capacity availability of the machines and manpower. The output of scheduling model 330 is a schedule 1330 which is a planned list of work orders 810 to be executed on each machine at a specified start data for a specified time duration. Another output of scheduling model 330 is performance measure 1340 (such as machine utilization, mean flow time, etc.) of the overall scheduling process. Such performance measures can be defined by the user when defining the scheduling model created by step 330 in FIG. 8.
The last step in FIG. 8 is to collect training data sets (step 360) from each run of the simulation experiments. Each training data set consists of the input and output from running work order 310 as well as the input and output from running scheduling model 330. These training data sets are later used to train the neural networks.
2. Knowledge Processor 120
The outputs of simulator 110 (FIG. 7) are data that represent production schedules as shown in step pointer 192 of FIG. 7. Before inputting these data into recurrent neural network 130 for training, they are first preprocessed. Similarly, during the recall phase of operation depicted in FIG. 11, input data from database 220 of FIG. 11 is also preprocessed. This is accomplished by knowledge processor 120 (FIG. 7) whose function is to provide an interface between neural network module 130 and database module 220. During the learning phase depicted in FIG. 7, data generated by simulator step 110 in the form of a schedule is pre-processed by knowledge processor 120 into the format recognized by recurrent neural network 130. This preprocessing involves translating and encoding the data into a series of codes such as binary codes or coarse conjunctive codes. The encoding process is based on the knowledge representation strategies used in representing scheduling input and output data in recurrent neural network 130. The rationale for using these representation strategies will be discussed in detail below. During the scheduling phase depicted by the method chart of FIG. 18, knowledge processor 120 (FIG. 7) is used to translate input data into neural network codes and also to translate neural network output codes into database format.
FIG. 19 shows the details of one exemplary embodiment of the operation of knowledge processor 120, which consists of two main components: encoder (preprocessor) 430 and decoder (post processor) 440. Referring now to FIG. 19, step pointer 192 indicates that an input file from simulator 110 of FIG. 7 is to be read by method step 410. Data are also read into a buffer from database 220 (FIG. 18), as shown in step 420. Once all the data are read into the buffer, the encoding process of step 430 begins. Input data can also be encoded one at a time as indicated by step pointer 293. Encoding process step 430 first converts scheduling input (i.e. work order 810) data such as part number, family group number, earliest start date, run time, etc. into binary codes. These binary codes are later fed to input layer 1810 (FIG. 6) of neural network 130 (FIG. 7). Next, encoding process step 430 continues to convert the scheduling output (i.e. a schedule) into coarse conjunctive codes. Specifically this is done for data such as setup time, machine number, and start/end time units. These conjunctive codes are later fed as desired output data to output layer 1830 (FIG. 6) of recurrent neural network 130 (FIG. 7). The converted data are then written to a file as shown in step 450 or input directly to neural network 130 for training or scheduling. The decoding process, as shown in step 440, functions as a post-processor for scheduling engine 260 (FIG. 11) to convert the scheduling output from neural network 130 (FIG. 7) to database format.
Knowledge processor 120 (FIG. 7) is, in one embodiment, implemented in the "C" language. In one embodiment, the design of knowledge processor 120 is integrated with recurrent neural network 130 (FIG. 7) and scheduling engine 260 (FIG. 11), although it need not be linked directly with simulator 110 and sequencer 240 as shown in FIG. 7 and FIG. 11, respectively.
3. Recurrent Neural Network 130 and Scheduling Knowledge Base 150
Recurrent neural network 130 in FIG. 7 is a facility that allows scheduling knowledge base 150 to be built using a learning method. The architecture of recurrent neural network 130 of the present invention is based on the recurrent neural network model which is designed to deal with time-varying data. A more detailed description of using a recurrent neural network for handling time-varying input or output is discussed in Williams and Zipser, "A Learning Algorithm for Continually Running Fully Recurrent Neural Networks", Neural Computation, Vol 1, pp 270-280, 1989, which is incorporated herein by reference. However, it should be understood that other time delay neural network models are equally applicable as well. Similar to the general neural network architecture as shown in FIG. 6, recurrent neural network 130 consists of layers of neurons, including an input layer 1810, one or more hidden layers 1820, and an output layer 1830. Neurons in input layer 1810 preferably use binary coding for representing scheduling input data. Neurons in output layer 1830, on the other hand, preferably use coarse conjunctive coding for representing scheduling output. The advantages of using this knowledge representation method will be clear when we describe scheduling knowledge base 150 below. There are connections from input layer 1810 to hidden layers 1820 and output layer 1830, and from hidden layers 1820 to output layer 1830. Additionally each neuron in hidden layers 1820 and output layer 1830 has a recurrent connection 1868 back to itself. These connections carry weights that collectively encode scheduling knowledge base 150.
An important issue to consider when using neural networks for solving complex problems is the design of such neural networks. The design of a neural network essentially involves the determination of the best network architecture. This includes decisions on such factors as how many hidden layers are required, how many neurons in each hidden layer, what learning coefficient is appropriate, etc. From the existing work, currently there is still lack of a systematic method which allows a designer to consider several key factors critical to a successful neural network design concurrently. The design of recurrent neural network 130 of the present invention is based on the Taguchi method. Using the Taguchi method, a neural network which is robust against initial weights condition during learning phase and insensitive to the architectural and input variations during recall phase can be achieved. A more detailed description of using the Taguchi method for neural network design is discussed in Khaw, Lim and Lim, "Using Taguchi Method for the Optimal Design of Neural Networks", paper submitted to Neural Networks, January 1993, which is incorporated herein by reference.
A key factor to consider when designing a neural network for scheduling is the knowledge representation strategy. Knowledge representation in neural networks is concerned with how concepts are represented in neural networks. There are many approaches to this. Some of them are distributed, in which each concept is represented by a pattern of micro features. Others are localist, in which single neurons are associated with concepts. Regardless of which approach is used, the causal relationship between concepts is represented by the strength of connections between them and the neural network as a whole constitutes the knowledge base. The examples of the present invention now described make use of binary coding for neurons in input layer 1810 and coarse conjunctive coding for neurons in output layer 1830. It should be noted that the use of binary coding and coarse conjunctive coding methods should be treated as the preferred methods in relation to the present invention. Other representation strategies can be used as well. Basically, binary coding is a method of decomposing a single input value into a series of codes in binary format. Examples of binary codes are shown in Table 1.
Coarse conjunctive coding, on the other hand, is a method of decomposing an output value into a series of codes based on the position of the value. Examples of coarse conjunctive codes are shown in Table 2.
As shown in FIG. 7, recurrent neural network 130 is designed to build scheduling knowledge base 150 through an adaptive learning (or training) process. It is trained by feeding training data which have been generated and encoded by simulator 110 and knowledge processor 120, respectively. A training data is composed of an input vector and a desired output vector. With reference to FIG. 6, training data is first presented to input layer 1810 as input vector 1818 and to output layer 1830 as desired output vector 1858. There are basically two methods to present training data to the neural network. One is to feed training data to the network in a random order while the other one is based on a sequential manner. Since a scheduling problem deals with sequences of events in a series of time steps, a sequential training approach is more appropriate. In the sequential approach, training data are fed to the network in a fixed sequence as specified in the training data itself.
Referring now to FIG. 6, input vector 1818 is presented to input layer 1810 and is propagated through to output layer 1830 to obtain output vector 1838. As this information propagates through the network, the new state of each neuron is also set using a set of equations. Examples of these equations for a standard summation function (equation 2) and a hyperbolic tangent transfer function (equation 3) are given below: ##EQU1##
It should be noted that other type of equations are equally applicable as well, for example a sigmoidal transfer function. Referring to FIG. 6, for each neuron in output layer 1830, calculate the scaled local error and delta weight using a method similar to the Generalized Delta Rule which is based on steepest descent method as follows:
where;
w.sub.ji,s is the weight 1828 from neuron j to neuron i;
s indicates the layer number;
j,s is the scaled local error of neuron j in layer s;
x.sub.i,s-1 is the current output value of the ith neuron in layer s-1; and
.alpha. is the learning coefficient.
The delta weights are then added to the corresponding previous weights 1828. This is repeated until the layer above input layer 1810 is reached. The learning progress of the network is monitored by means of statistical instruments such as root-mean-squared error graph, weights distribution histogram, etc. After a large number of presentation of the input vectors 1818, the network will converge to a solution that minimizes the difference between the desired output 1858 and measured network output 1838.
FIG. 16 is a detailed block diagram which shows the types of data used in one embodiment of this invention to train recurrent neural network 130. As shown in FIG. 16, a set of training data from training data sets 1510 which form work order lists 810 and a set of training data from training data sets 1520 which form schedules 1330 is fed to input layer 1810 and output layer 1830, respectively, of recurrent neural network 130 for training. Once neural network 130 converges, another set of training data from training data sets 1510 and 1520 are then used for training. This process is repeated until all the training data sets have been used for training recurrent neural network 130. At this point, scheduling knowledge base 150, which was initialized to random values in the beginning of training, has been exposed to the various scheduling patterns. Scheduling knowledge base 150 is now said to have learned and it now contains the scheduling knowledge which is spread throughout its connection weights, which connection weights are then fixed. Although scheduling knowledge base 150 is domain specific, it generally includes heuristics to assign machines to schedule work orders, heuristics to determine the number of machine setups required, and heuristics to determine start and end times of work orders.
4. Feedforward Neural Network 135 and Operational Policy Knowledge Base 140
Feedforward neural network 135 (FIG. 7) is a facility which allows operational policy knowledge base 140 to be built using a learning method. The architecture of feedforward neural network 135 of the present invention preferably is based on the back-propagation neural network model. A more detailed description of back-propagation neural network model is given in McClelland and Rumelhart, "Parallel Distributed Processing: Explorations in the Microstructure of Cognition". The MIT Press, 1986, which is incorporated herein by reference. Similar to the recurrent neural network 130 discussed above with reference to FIG. 6, neural network 135 has a multi-layer architecture which includes an input layer, one or more hidden layers, and an output layer. All the neurons in a layer are fully connected to the adjacent layer(s). Each neuron has a similar set of equations such as equations [2], [3], and [4] above. Feedforward neural network 135 is designed and is trained using the same learning method as described above with respect to recurrent neural network 130.
As shown in FIG. 17, a set of training data from training data sets 1410 (which represent machine workload 1210 and performance goals 1340) and a set of training data from training data sets 1420 (which represent operational policy 12230) are used to train neural network 135. These training data sets are generated from simulator 110 (FIG. 7) for training neural network 135 whose purpose is to address the complexity of sequencing decisions based on multiple criteria with often conflicting consequences. After neural network 135 is trained, it is capable of mapping the complex relationships between the desired characteristics of the sequencing solutions and the relative importance of the scheduling criteria. As will be discussed in greater detail below, these scheduling criteria or operational policies are used to determine the rank of each work order 810 for scheduling.
5. User Interface 210, Database 220, and Charts/Reports 230
FIG. 18 shows a high level diagram which can be used to implement the scheduling method of the present invention. The method steps shown in FIG. 18 control the operation of the preferred architecture of the present invention which is shown in FIG. 5. Referring now to FIGS. 11 and 5, a first method step serves to develop user interface module 210. User interface module 210 is a general type of graphical user interface which, in general, includes an order entry screen that allows users to enter new work order 810 information; screens for defining various types of constraints such as work center, machine, part, tooling, and calendar; and a screen that allows users to define various scheduling parameters before a scheduling process is performed. All the screens preferably provide functions for data maintenance such as adding, deleting, copying, listing, saving, printing, etc.
As shown in FIGS. 181 and 5, database 220 is a facility to store static data such as constraint data as entered from the constraint screens and dynamic data such as existing machine schedule. Database 220 is also a tool for organizing, managing, and retrieving these data. Database 220 further serves as a place to interface with an external database, if the need arises. Database 220 can be conveniently developed using a commercial database tool or a spreadsheet package such as Microsoft Excel, a product of Microsoft Corporation of Redmond, Wash., USA.
Also shown in FIGS. 18 and 5 is charting/reporting module 230, which provides a convenient method of presenting visual displays of scheduling input and output data in a meaningful way. For example, standard Gantt charts can be used to provide a graphical representation of a schedule. In addition, users can view and print many types of production reports provided by this module as desired. 6. Sequencer 240
Neural network module 1910 as shown in FIG. 5 includes sequencer 240, knowledge processor 120, and scheduling engine 260 which together are used to generate final schedule 270 as shown in FIG. 18. Sequencer 240 receives from database 220 a list of work orders 810 to be scheduled, and ranks and sorts all these work orders 810 in a priority sequence. As will be discussed in detail below, sequencer 240 consists of feedforward neural network 135 previously trained to make operational policies. It should be noted that trained feedforward neural network 135 consists of an operational policy knowledge base 140 which is stored in connection weights spread over the entire network. Although other methods such as the simple scoring method, analytical hierarchy process, or scheduling heuristics can be used to achieve the same objective, the neural network approach is employed here for its capability to map the relationships between the desired characteristics of the scheduling solutions and the operational policies for the work orders. Using the output of trained feedforward neural network 640 (FIG. 20), a priority index is determined for each work order and these work orders are then listed according to their priority indices.
FIG. 20 is a detailed block diagram of one embodiment of sequencer 240 of the present invention. Step pointer 291 as shown in FIG. 15 indicates that list of work orders 810 to be scheduled and constraints 850 are input to sequencer 240 in parallel. Constraints 850 are machine workload 1210, and performance goals 1340, as shown in FIG. 21. As shown in step 640 of FIG. 15, constraints 850 are fed to feedforward neural network 135, previously trained to establish the relationship between the relative importance of scheduling criteria and the overall performance of the factory floor, to obtain operational policies 1220 (FIG. 21) for a work order 810.
FIG. 21 shows, in detail, the types of data used and generated by sequencer 240. With reference to FIG. 21, machine workload 1210 data can be determined from the load of the existing schedule which is available from database module 220. Performance goals 1340 are user-defined parameters as discussed above with respect to simulator 110 (FIG. 7). These data represent global scheduling parameters which will affect the final schedule 270 generated. The output of the trained neural network 640 is operational policies 1220 which reflects the relative importance of different scheduling criteria used. As shown in step 620 in FIG. 20, a work order is selected at random from the work order list 810 to calculate the priority index of the work order using the operational policies and equation [1] above (step 660). All the work orders 810 are then sorted according to their priority index and they are written a file as shown in step 680 in FIG. 20. These sorted work orders 810 are later used for scheduling.
7. Scheduling Engine 260
Referring to FIG. 18, before inputting to scheduling engine 260 for scheduling, the list of sorted work orders 810 are preprocessed by knowledge processor 120 as indicated by step pointer 293. After preprocessing of work orders 810 is completed, the work order at the top of the list is then fed to scheduling engine 260 for scheduling. As shown in Figure 28, scheduling engine 260 is embedded with a recurrent neural network 130 previously trained to build a scheduling knowledge base 150 and a competitive neural network 1700. In other words, scheduling engine 260 is a system of two neural networks and together they are used to solve the dynamic scheduling problem. New to the scheduling engine 260 of the present invention is competitive neural network 1700 which can be implemented using the interactive activation and competitive model. It should be understood that the use of interactive activation and competitive network is not exclusive to the present invention. Other types of competitive neural networks such as the Boltzmann machine are applicable as well. A more detailed description of Boltzmann machine can be found in Ackley, Hinton, and Sejnowski, "Learning and Relearning in Boltzmann Macines" in Parallel Distributed Processing: Volume 1 Foundation, edited by McClelland and Rumelhart, MIT Press, 1988.
An interactive and competitive network consists of a collection of neurons organized into some number of competitive pools. There are excitatory connections among neurons in different pools and inhibitory connections among neurons within the same pool. This organization allows neurons in different pools to interact with one another and neurons within the same pool to compete with one another. The updating equations for summation and transfer functions are given in [5] and [6] below: ##EQU2##
If net.sub.i >0, .DELTA.a.sub.i =net.sub.i (max-a.sub.i)-decay(a.sub.i -rest) (6)
where;
max=1, min<rest<0, and 0<decay<1
The decay rate determines how fast the stable condition is reached. The recommended values are max=1, min=-0.2, rest=0, and decay=0.07. A full description of this particular network can be found in James L. McClelland and David E. Rumelhart, "Explorations in Parallel Distributed Processing: A Handbook of Models, Programs, and Exercises", MIT Press, 1988.
The neurons in the interactive activation and competitive network of the present invention are organized into a number of pools such as setup time pool, machine pools, and time unit pools. The trained recurrent neural network 130 is linked with the competitive network 1700 via corresponding connections from the output layer of the recurrent neural network 130 to the pools of the interactive activation and competitive network. In addition there are connections between the input layer of the recurrent neural network 130 and the interactive and competitive network.
The scheduling approach of the present invention is based on sequential assignment paradigm which builds up final schedule 270 from a partial schedule incrementally. As shown by step pointer 293 of FIG. 18, a work order 810 from sequencer 240 is selected for scheduling. The work order is then encoded by knowledge processor 120 and fed to scheduling engine 260. Referring now to FIG. 22, scheduling of work orders 810 by scheduling engine 260 begins with selecting a work order from an input file to schedule (step 510). The work order and together with capacity availability data, which represents input vector 1818 of FIG. 6, is first fed to trained recurrent neural network 130 (step 520). FIG. 23 shows a more detailed figure of step 520. Before input vector 1818 is read into the neural network, the processing counter is reset to a predefined value. This counter is used by competitive neural network 1700 to determine the number of cycles needed for interaction and competition. The input vector is then read into the input layer of trained recurrent neural network 130 (steps 2020 and 2030).
From the input layer of trained recurrent neural network 130, input vector 1818 are passed forward to the next layer after having been processed by a set of equations, e.g. equations (2) and (3) taking into account of connection weights 1828 of FIG. 6 between the layers (steps 2120 and 2130 of FIG. 24). This process is repeated until the output layer of trained recurrent neural network is reached. The output of the output represents possible schedules for the work order. These output are subsequently propagated to competitive neural network 1700 for determining the best schedule among the possible schedules. It should be noted that the trained recurrent neural network 130 consists of a scheduling knowledge base which is stored in connection weights 1828 (FIG. 6) spread over the whole network. These connection weights are fixed during the recall or scheduling phase.
Once the possible schedules have been calculated, step pointer 1825 in FIG. 22 shows that the schedules are used to determine the best schedule (step 540). Referring now to FIG. 25, the next stage of the scheduling process is set at the competitive neural network 1700. Before competitive neural network 1700 begins processing, its connection weights must be setup (step 2220). This involves special connections 1878 (FIG. 6) which are affected by the input vector 1818. Excitatory or inhibitory weights are assigned to these connections as appropriate. For example, all connections which relate to the same part number of the work order being scheduled are assigned with excitator (positive) values. After connection weights are properly setup, then interactive and competitive process (step 2230) can begin. This process continues until the processing counter is equal to zero. After which the output of the processing is determined (step 2250). A specific example of the details for steps 2220, 2230, and 2250 is given in software listing 3 of the Appendix.
When a work order assignment is not successful, then soft constraints can be relaxed. In this invention, soft constraints are divided into priority groups by their importance. Relaxation of soft constraints will proceed from the least important group to the most important group. As shown in FIG. 26, relaxation of constraints involves first identifying the connections that represent the constraints (step 720) and then restoring the connection weights to the fixed weights as stored in the scheduling knowledge base 150 (step 730). Unsuccessful work order assignment can still arise after constraint relaxation. In this situation, human intervention is required (step 740). The user intervention module allows a user to delete a previous assignment from the schedule or add a new assignment for a work order into the schedule. Typical examples of the messages from the user intervention module are rescheduling of existing work orders, change of the order's customer need dates, and/or increase of manpower capacity.
Referring to FIG. 22, after the best schedule has been determined, relevant connection weights must be updated to reflect new scheduling constraints (step 550). A more detailed description of this process is given in FIG. 27. As shown in step 2310 of FIG. 27, the processing layer is again set at the competitive neural network 1700. All variable weights related to the output (step 2250 in FIG. 25) is first initialized. The appropriate excitatory or inhibitory values are then assigned to the connection weights (steps 2330 and 2340). For example, after a work order is assigned to machine A from time unit 10 to time unit 20, then other work orders are not allowed to use machine A from time unit 10 to time unit 20 anymore. A large inhibitory or negative weight is assigned to the appropriate connection to enforced this constraint. FIG. 28 shows the details of the input data used and output data generated by trained recurrent neural network 130 and competitive neural network 1700. A specific example of the details for steps 2320, 2330, and 2340 is given in software listing 3 of the Appendix.
Those skilled in the art, having the benefit of the teachings of the present invention as herein above set forth may effect numerous modifications thereto. It should be understood that such modifications are to be construed as lying within the contemplation of the present invention as defined by the appended claims.
All publications and patent applications mentioned in this specification are herein incorporated by reference to the same extent as if each individual publication or patent application was specifically and individually indicated to be incorporated by reference. ##SPC1##
Claims
What is claimed:
1. A computer neural network scheduling system adapted for scheduling of a manufacturing resource on a factory floor, the scheduling process producing a schedule for a list of work orders given the manufacturing resource having at least one machine, the scheduling system comprising: a sequencer, for sorting said list of work orders in a sequence for scheduling in accordance with a work orders priority index;. a scheduling engine, for producing a schedule for a sequence of work orders in accordance with said sorted list of work orders and capacity of said manufacturing resource, comprising: a trained recurrent neural network, comprising a scheduling knowledge base, for predicting possible schedules for said sequence of work orders in accordance with said sorted list of work orders and said capacity of manufacturing resource and in accordance with weights; a competitive neural network, responsive to said trained recurrent neural network, for producing a schedule in accordance with said sorted list of work orders; and a constraint relaxation module, responsive to said competitive neural network, for relaxing constraints in the event of an unsuccessful assignment of a work order; and knowledge processor, comprising: an encoder, responsive to said sequencer, for encoding said sorted list of work orders and capacity of said manufacturing resource to a neural network format for input into said scheduling engine; and a decoder, responsive to said scheduling engine, for decoding said schedule from said scheduling engine into a format suitable for storage into a database.
2. The computer neural network scheduling system of claim 1, wherein said sequencer comprises: a trained feedforward neural network, comprising an operational policy knowledge base, for determining operational policies in accordance with machine workload and performance measure; and means for calculating said priority index in accordance with said operational policies for each of said work orders.
3. The system as in claim 1 further comprising: first connections for connecting an input layer of said trained recurrent neural network to an output layer of said competitive neural network; means for setting up weights of said first connections in accordance with a work order from said sorted list of work orders and in accordance with said capacity of manufacturing resource prior to scheduling of said work order; means for updating said weights of said first connections in accordance with output of said competitive neural network after scheduling of said work order; and second connections, between an output layer of said trained recurrent neural network and an output layer of said competitive neural network, for propagating said possible schedules to said competitive neural network.
4. The system as in claim 1, wherein said competitive neural network further comprises means for neurons to interact and compete among themselves to determine output, that represent said schedule, in accordance with said weights from said first connections and in accordance with said possible schedules from said second connections.
5. The system as in claim 1, wherein said constraint relaxation module further comprises a user intervention module for allowing a user to interact with said scheduling process directly.
6. A computer-based scheduling method adapted for scheduling of manufacturing resource on a factory floor, the scheduling process producing a schedule for a list of work orders given the manufacturing resource having at least one machine, the computer-based scheduling method comprising the steps of: (a) determining/generating operational policies from a trained feedforward neural network using machine workload and performance measure as input; (b) calculating a priority index of each said work order using said operational policies; (c) sorting said list of work orders in accordance with said priority index; (d) selecting a work order with the highest said priority index from said sorted list of work orders; (e) initializing weights, for connections between an input layer of a trained recurrent neural network and an output layer of a competitive neural network in accordance with said selected work order and in accordance with a capacity of said manufacturing resource; (f) predicting possible schedules in accordance with said selected work order and in accordance with a capacity of said manufacturing resource, said predicting being performed by said trained recurrent neural network; (g) determining outputs that represent a schedule by allowing neurons in the competitive neural network to interact and compete among themselves in accordance with said weights and in accordance with said possible schedules, said determining being performed by said competitive neural network; (h) updating said weights for connections between an input layer of said trained recurrent neural network and an output layer of said competitive neural network in accordance with said output; and (i) selecting a next work order with the next highest priority index from said sorted list of work orders and repeating steps (e) to (h) until all said work orders are scheduled.
7. The computer-based scheduling method of claim 6, further comprising a method for handling situations when a work order assignment is unsuccessful, the method comprising the steps of: relaxing soft constraints, starting with the least important group of constraints, when an assignment is not successful by restoring said weights that represent the said constraint group to their initial values; and allowing a user to interact with said scheduling process when no more said group of constraints can be relaxed.
8. A computer neural network scheduling system adapted for scheduling of manufacturing resource on a factory floor, the scheduling process producing a schedule for a list of work orders given the manufacturing resource having at least one machine, the scheduling system comprising: a sequencer, for sorting said list of work orders in a sequence for scheduling in accordance with a work orders priority index; a scheduling engine, for producing a schedule for a sequence of work orders in accordance with said sorted list of work orders and capacity of said manufacturing resource, comprising: a trained recurrent neural network, comprising a scheduling knowledge base, for predicting possible schedules for said sequence of work orders in accordance with said sorted list of work orders and said capacity of manufacturing resource and in accordance with weights; a competitive neural network, responsive to said trained recurrent neural network, for producing a schedule in accordance with said sorted list of work orders; and a constraint relaxation module, responsive to said competitive neural network, for relaxing constraints in the event of an unsuccessful assignment of a work order; and a knowledge of processor, comprising: an encoder, responsive to said sequencer, for encoding said sorted list of work orders and capacity of said manufacturing resource to a neural network format for input into said scheduling engine; and a decoder, responsive to said scheduling engine, for decoding said schedule from said scheduling engine into a format suitable for storage into a database.
9. The computer neural network scheduling system of claim 8, wherein said sequencer comprises: a trained feedforward neural network, comprising an operational policy knowledge base, for determining operational policies in accordance with machine workload and performance measure; and a calculation mechanism for calculating said priority index in accordance with said operational policies for each of said work orders.
10. The system of claim 9 wherein said trained feedforward neural network further comprises: a learning mechanism, responsive to training data for adjusting weights, to produce said operational policy knowledge base; a predicting mechanism, responsive to said operational policy knowledge base, for predicting said operational policies in accordance with input data and in accordance with said weights; and an input mechanism for entering training data comprising typical machine workload, performance measure, and corresponding operational policies.
11. The system of claim 8 wherein said trained recurrent neural network further comprises: an input mechanism for entering said training data comprising typical work orders, capacity of said manufacturing resource, and corresponding schedules; a learning mechanism, responsive to training data for adjusting weights, for producing a scheduling knowledge base; and a predicting mechanism, responsive to said scheduling knowledge base, for predicting schedules in accordance with said weights.
12. The system as in claim 8 further comprising: first connections, for connecting an input layer of said trained recurrent neural network and an output layer of said competitive neural network; a first determination mechanism for setting up weights of said first connections in accordance with a work order from said sorted list of work orders and in accordance with said capacity of manufacturing resource prior to scheduling of said work order; a second determination mechanism for updating said weights of said first connections in accordance with output of said competitive neural network after scheduling of said work order; and second connections, between an output layer of said trained recurrent neural network and an output layer of said competitive neural network, for propagating said possible schedules to said competitive neural network.
13. The system as in claim 8, wherein said competitive neural network further comprises a mechanism allowing neurons to interact and compete among themselves to determine output, that represent said schedule, in accordance with said weights from said first connections and in accordance with said possible schedules from said second connections.
14. The system as in claim 8, wherein said constraint relaxation module further comprises a user intervention module for allowing a user to interact with said scheduling process directly.
15. The computer neural network scheduling system of claim 8, further comprising a computer-based simulator for modeling said scheduling process for generating said training data.
16. The system of claim 15 wherein said computer-based simulator comprises: a first modeling means, for modeling the creation of said sorted list of work orders, in accordance with machine workload and operational policies; a second modeling means, responsive to said sorted list of work orders, for modeling scheduling logic of human expert schedulers of said factory floor to produce a schedule and their corresponding performance measures in accordance with said capacity of manufacturing resource; and means for sorting a list of work orders according to a priority index determined from said operational policies.
17. A neural network based scheduling method adapted for scheduling of a manufacturing resource on a factor floor, the scheduling process producing a schedule for a sorted list of work orders given the manufacturing resource having at least one machine, the neural network based scheduling method comprising the steps of: (a) selecting a work order from a sorted list of work orders; (b) initializing weights for connections between an input layer of a first trained neural network and an output layer of a second trained neural network in accordance with said selected work order and in accordance with a capacity of said manufacturing resource; (c) predicting possible schedules in accordance with said selected work order and in accordance with said capacity of said manufacturing resource, said predicting being performed by said first neural network; (d) determining output that represents a schedule by allowing neurons in said second trained neural network to interact and compete among themselves in accordance with said weights and in accordance with said possible schedules, said determining being performed by said second neural network; (e) updating said weights for connections between an input layer of said first trained neural network and an output layer of said second trained neural network in accordance with said output; and (f) selecting a next work order from said sorted list of work orders and repeating steps (a) to (e) until all said work orders are scheduled.
18. The computer-based scheduling method of claim 17, further comprising a method for handling situations when a work order assignment is unsuccessful, comprising the steps of: relaxing soft constraints, starting with the least important group of constraints, when an assignment is not successful by restoring said weights that represent the said constraint group to their initial values; and allowing a user to interact with said scheduling process when no more said group of constraints can be relaxed.
19. The computer-based scheduling method of claim 17 wherein said sorted list of work is produced using the steps of: determining/generating operational policies from a third trained neural network using machine workload and performance measure as input; calculating a priority index of each said work order using said operational policies; and sorting said work orders in accordance with said priority index.
20. A computer neural network scheduling system adapted for scheduling of a manufacturing resource on a factory floor, the scheduling process producing a schedule for a sorted list of work orders given the manufacturing resource having at least one machine, the computer neural network scheduling system comprising: a first neural network, comprising a scheduling knowledge base, for predicting possible schedules for said sorted list of work orders in accordance with a capacity of said manufacturing resource and a first set of weights; a second neural network, responsive to said first neural network, for producing a schedule in accordance with said sorted list of work orders and said capacity of said manufacturing resource and in accordance with a second set of weights; a constraint relaxation module for relaxing constraints by adjusting said second set of weights in the event of unsuccessful assignment of a work order; first connections for connecting an input layer of said first neural network and an output layer of said second neural network; a first determination mechanism for setting up weights of said first connections in accordance with a work order from said sorted list of work orders and in accordance with said capacity of said manufacturing resource prior to scheduling of said work order; a second determination mechanism for updating said weights of said first connections in accordance with output of said second neural network after scheduling of said work order; and second connections, between an output layer of said first neural network and an output layer of said second neural network, for propagating said possible schedules to said second neural network.
21. The system of claim 20 wherein said first neural network further comprises: an input mechanism for entering training data comprising typical work orders, capacity of said manufacturing resource, and corresponding schedules; a learning mechanism, responsive to said training data for adjusting weights, for producing a scheduling knowledge base; and a predicting mechanism, responsive to said scheduling knowledge base, for predicting schedules in accordance with said sorted list of work orders and said capacity of said manufacturing resource and in accordance with said first set of weights.
22. The system as in claim 20 wherein said second neural network further comprises a mechanism allowing neurons to interact and compete among themselves to determine output which represents said schedule, in accordance with said first set of weights from said first neural network and in accordance with said possible schedules from said second neural network.
23. The system as in claim 20 wherein said constraint relaxation module further comprises a user intervention module for allowing a user to interact with said scheduling process directly.
24. The computer neural network scheduling system of claim 20, further comprising a computer-based simulator for modeling said scheduling process for generating said training data.
25. The system of claim 24 wherein said computer-based simulator comprises: a first modeling means, for modeling the creation of said sorted list of work orders, in accordance with machine workload and operational policies; a second modeling means, responsive to said sorted list of work orders, for modeling scheduling logic of human expert schedulers of said factory floor to produce a schedule and corresponding performance measures in accordance with said capacity of manufacturing resource; and means for sorting a list of work orders according to a priority index determined from said operational policies.
26. A computer neural network scheduling system adapted for scheduling of a manufacturing resource on a factory floor, the scheduling process producing a schedule for a list of work orders given the manufacturing resource having at least one machine, the computer neural network scheduling system comprising: a trained feedforward neural network, comprising an operational policy knowledge base, for determining operational policies in accordance with machine workload and performance measure; a calculation mechanism, responsive to said operational policies, for calculating a priority index of each work order for sorting said list of work orders; a trained recurrent neural network, comprising a scheduling knowledge base, for predicting possible schedules in accordance with said sorted list of work orders and a capacity of said manufacturing resource and in accordance with a first set of weights; a competitive neural network, responsive to said trained recurrent neural network, for producing a schedule in accordance with said sorted list of work orders and said capacity of manufacturing resource and in accordance with a second set of weights; and a constraint relaxation module, for relaxing constraints by adjusting said second set of weights in the event of an unsuccessful assignment of a work order.
27. The system of claim 26 wherein the trained recurrent neural network further comprises: an input mechanism for entering training data comprising typical work orders, capacity of manufacturing resource, and corresponding schedules; a learning mechanism, responsive to said training data, for adjusting said first set of weights, for producing said scheduling knowledge base; and a predicting mechanism responsive to said scheduling knowledge base, for predicting schedules in accordance with said sorted list of work orders and said capacity of manufacturing resource and in accordance with said first set of weights.
28. The system of claim 26 further comprising: first connections, for connecting an input layer of said trained recurrent neural network and an output layer of said competitive neural network; a first determination mechanism for setting up weights of said first connections in accordance with a work order from said sorted list of work orders and in accordance with said capacity of manufacturing resource prior to scheduling of said work order; a second determination mechanism for updating said weights of said first connections in accordance with output of said competitive neural network after scheduling of said work order; and second connections, between an output layer of said trained recurrent neural network and an output layer of said competitive neural network, for propagating said possible schedules to said competitive neural network.
29. The system as in claim 26, wherein said competitive neural network further comprises a mechanism allowing neurons to interact and compete among themselves to determine output, that represent said schedule, in accordance with said weights from said first connections and in accordance with said possible schedules from said second connections.
30. The system as in claim 26, wherein said constraint relaxation module further comprises a user intervention module for allowing a user to interact with said scheduling process directly.
31. A computer neural network scheduling system adapted for scheduling of a manufacturing resource on a factory floor, the scheduling producing a schedule for a list of work orders given the manufacturing resource having at least one machine, the computer neural network scheduling system comprising: a first neural network, comprising an operational policy knowledge base, for determining operational policies in accordance with machine workload and performance measure; a calculation mechanism, responsive to said operational policies, for calculating a priority index of each work order for sorting said list of work orders; a second neural network, comprising a scheduling knowledge base, for predicting possible schedules in accordance with said sorted list of work orders and capacity of said manufacturing resource and in accordance with a first set of weights; a third neural network, responsive to said second trained neural network, for producing a schedule in accordance with said sorted list of work orders and said capacity of manufacturing resource and in accordance with a second set of weights; a constraint relaxation module, for relaxing constraints by adjusting said second set of weights in the event of an unsuccessful assignment of a work order; first connections, for connecting an input layer of said second neural network and an output layer of said third neural network; first determination mechanism for setting up weights of said first connections in accordance with a work order from said sorted list of work orders and in accordance with said capacity of manufacturing resource prior to scheduling of said work order; a second determination mechanism for updating said weights of said first connections in accordance with output of said third neural network after scheduling of said work order; and second connections, between an output layer of said second neural network and an output layer of said third neural network, for propagating said possible schedules to said third neural network.
32. The system of claim 31 wherein the second neural network further comprises: an input mechanism for entering training data comprising typical work orders, capacity of manufacturing resource, and corresponding schedules; a learning mechanism, responsive to said training data for adjusting said first set of weights, for producing said scheduling knowledge base; and a predicting mechanism responsive to said scheduling knowledge base, for predicting schedules in accordance with said sorted list of work orders and said capacity of manufacturing resource and in accordance with said first set of weights.
33. The system as in claim 31, wherein said third neural network further comprises a mechanism allowing neurons to interact and compete among themselves to determine output that represents said schedule, in accordance with said weights from said first connections and in accordance with said possible schedules from said second connections.
34. The system as in claim 31, wherein said constraint relaxation module further comprises a user intervention module for allowing a user to interact with said scheduling process directly.
Patent Citations (4)
Non-Patent Literature (14)
- Rabelo et al, "Adaptive Scheduling and Control Using ANN and Expert Systems for a Hierarchical/Distributed FMS Architecture", Proc of Rensseloer's Int'l Conf on CIM, May 21-23 1990, pp. 538-545.
- Zhang et al, "Solving Job-Shop Scheduling Problem with Priority Using Neural Network", 1991 IEEE Int'l Joint Conf on Neural Networks, Nov. 18-21 1991, pp. 1361-1366.
- Foo et al, "Stochastic Neural Networks for Solving Job Shop Scheduling: Part I Problem Representation", IEEE Int'l Conf on Neural Networks, Jul. 24-27 1988, pp. 275-282.
- Ghryssolouris et al, "The Use of Neural Networks in Determining Operational Policies for Manufacturing Systems", pp. 166-175.
- Stottler et al, "Automatic Translation from an Expert System to a Neural Network Representation", Int'l Joint Conf on Neural Networks, Jun. 7-11 1992 pp. 13-20 vol. 1.
- "The Gaussian Machine: A Stochastic Neural Network for Solving Assignment Problems", Akiyama et al., Journal of Neural Network Computer, pp. 43-51.
- "Scaling Neural network for Job-Shop Scheduling", Zhou et al, Abstract Paper of Dept. of Energy and Transportation.
- Using the Taguchi Paradigm for Manufacturing System Design Using Simulation Experiments, R. J. Mayer, Computers Ind. Engng., vol. 22, No. 2, pp. 195-209.
- "Stochastic Neural Networks for Solving Job-Shop Scheduling: Part 1. Problem Presentation", Foo et al., University of S. Carolina Abstract Paper.
- Job Shop Scheduling by Simulated Annealing, paper by Peter J. M. Van Laarhoven Centre for Quantitative Methods, Nederlandse Philips.
- A Goal Programming Network for Mixed Integer Linear Programming: A Case Study for the Job-Shop Scheduling Problem, Int. Jrnl of Neural Systems, 2:3, 201-209.
- A Timetable Scheduling Using Neural Networks with Parallel Implementation on Transputers, Lim et al., Inst of Systems Science.
- The Use of Neural Networks in Determining Operational Policies for Manufacturing Systems, Ghryssolouris et al., pp. 166-175.
- Scheduling for Minimizing Total Actual Flow Time by Neural Networks Arizono et al., Int. Jrn. Prod. Res., 1992, vol. 30, No. 3 pp. 503-511.