Neural network system and method for factory floor scheduling

• US 5,432,887 A
• Filed: 03/16/1993
• Issued: 07/11/1995
• Est. Priority Date: 03/16/1993
• Status: Expired due to Fees

• Current Assignee: Singapore Computer Systems Limited (Singapore Telecommunications Limited)
• Original Assignee: Singapore Computer Systems Limited (Singapore Telecommunications Limited)
• Inventors: Khaw, Fook C.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): SHAPIRO, STUART
• Application Number:
  US08/031,954
• Time in Patent Office: 847 Days
• Field of Search: 395/11, 395/22, 395/73, 395/26
• US Class Current: 706/19
• CPC Class Codes: G06N 3/042 Knowledge-based neural networks; Logical representations of neural networks
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

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.

Claims

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.