Scheduling method and system

• US 5,524,077 A
• Filed: 12/04/1989
• Issued: 06/04/1996
• Est. Priority Date: 07/24/1987
• Status: Expired due to Term

• Current Assignee: Bruce H. Faaland, Thomas G. Schmitt
• Original Assignee: Bruce H. Faaland, Thomas G. Schmitt
• Inventors: Faaland, Bruce H., Schmitt, Thomas G.
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Kyle, Charles R.
• Application Number:
  US07/445,479
• Time in Patent Office: 2,374 Days
• Field of Search: 364/401, 364/402, 364/152, 364/153, 364/156, 364/468, 364/478
• US Class Current: 705/7.21
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/1097 Task assignment
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

This invention provides a method and system for cost-based resource scheduling. This invention develops an initial resource schedule. This schedule is then represented as a Schedule Precedence Graph, which is an acyclic directed graph consisting of nodes and arcs. Each node corresponds to a task to be performed, and each arc corresponds to a technological or assigned task precedence. Each node is assigned a cost, which corresponds to cost or savings due to delaying the task one time unit. In this invention, the Maximum Flow Procedure is iteratively invoked to determine which tasks can be profitably delayed.

Claims

1. An apparatus for scheduling a combination of workers, tasks, and work centers, comprising:

means for storing schedule and task information, delayed delivery costs, and inventory carrying costs;

means for generating an initial schedule based on the schedule and task information whereby workers are assigned to perform tasks at work centers; and

means for modifying the initial schedule based on the delayed delivery costs and inventory carrying costs whereby the start of at least two tasks are delayed when the delayed delivery cost of at least one end-product task is offset by the inventory carrying cost savings due to delaying the start of other tasks.

2. A method for reallocating a combination of workers, tasks, and work centers based on an initial allocation schedule, each task having an associated start time and an associated inventory carrying cost, each end-product task having an associated delayed delivery cost whereby the start of at least two tasks are delayed when the delayed delivery cost of at least one end-product task is offset by the inventory carrying cost savings due to delaying the start of other tasks, the method comprising the steps of:

developing a Technological Precedence Graph based on product design, whereby the Technological Precedence Graph includes a plurality of nodes representing tasks and directed arcs connecting the nodes and defining technological precedence;

developing a Schedule Precedence Graph based on the initial allocation schedule and Technological Precedence Graph additionally including arcs defining nonredundant schedule precedence;

assigning each node in the Schedule Precedence Graph a supply value representing the cost of carrying inventory and delaying delivery;

adding a fictitious node to the Schedule Precedence Graph for each end-product task scheduled for early delivery;

assigning to each arc an initial capacity of zero in the arc direction and an infinite capacity in the direction opposite the arc;

initializing a Facility Queue to contain nodes based on the Schedule Precedence Graph;

selecting and removing the top node from the Facility Queue;

determining whether the selected node has been on a Candidate List;

generating the Candidate List of nodes based on the Schedule Precedence Graph and the selected node;

generating a Move List and a Stay List of nodes based upon the Candidate List;

revising the cumulative delay of the nodes in the Move List;

recording the start times of the nodes in the Stay List; and

reallocating the combination of workers, tasks, and work centers in accordance with the start time of the tasks and performing the tasks in accordance with the reallocation.

3. The method of claim 2 wherein the step of generating a Move List of nodes comprises the Maximum Flow Procedure.

4. The method of claim 2 wherein the step of generating the Move List and the Stay List of nodes, each node has an associated MFP backtrack label, and additionally includes the steps of:

initializing a Go Queue to contain all the facility nodes that are in the Candidate List;

selecting a node from the Go Queue;

labeling the selected node;

when possible, selecting a second node adjacent to the selected node to receive flow;

sending flow to the second selected node from the selected node;

when the supply of the second selected node is greater than zero, making such node the new selected node;

when the supply of the selected node is not greater than zero, backtracking to the closest node having supply greater than zero or the original selected node, whichever is encountered first, and selecting such node as the new selected node;

removing the label from all backtracked nodes;

when no second selected node exists, sending flow back from the selected node to the node pointed to by the MFP backtrack label and selecting the node pointed to by the MFP backtrack label as the new selected node;

when no second selected node exists and the selected node is the original selected node, placing all nodes with a label from this iteration on the Stay List; and

when the Go Queue is empty, placing all nodes that are on the Candidate List and that are not on the Stay List onto a Move List.

5. A method according to claim 4 wherein the step of initializing the Go Queue includes the step of organizing the nodes into a heap data structure.

6. A method according to claim 2 wherein the schedule to be modified is an Early Finish Schedule.

7. A method according to claim 2 wherein the schedule to be modified is a Late Finish Schedule.

8. A method according to claim 2 wherein the step of initializing of the Facility Queue additionally includes the step of adding all the facility nodes in the Schedule Precedence Graph into the Facility Queue.

9. A method according to claim 2 wherein the step of initializing the Facility Queue additionally includes the step of adding each node that is an activity node in the Schedule Precedence Graph into the Facility Queue.

10. A method according to claim 2 wherein the steps of initializing the Facility Queue additionally includes the steps of organizing the Facility Queue as a heap data structure.

11. The method of claim 2 wherein the step of revising the cumulative delay of the nodes in the Move List, each node having an associated MFP backtrack label, additionally includes the steps of:

initializing a Move Queue to contain no arcs;

adding to the Move Queue those arcs not already in the Move Queue whose tail node is in the Move List and whose head node is not in the Move List;

removing from the Move Queue those arcs whose tail nodes are in the Stay List;

selecting and removing the top arc from the move Queue;

setting the cumulative delay of the Move List equal to the length of the selected arc;

determining whether the node to which the selected arc points is labeled;

backtracking from the labeled node to a node with an MFP backtrack label of nil;

while backtracking, placing nodes pointed to by the MFP backtrack labels into the Candidate List; and

determining whether the tail node of the selected arc is in the Stay List.

12. The method of claim 11 wherein the step of adding the arcs to the Move Queue additionally includes the step of setting the length of the arc equal to the sum of the cumulative delay of the Move List, and the length of time between the start of the head node and the completion of the tail node.

13. The method according to claim 11 wherein step of initializing the Move Queue additionally includes the step of organizing the Move Queue as a heap data structure.

14. A resource allocation system for controlling the allocation of workers, work centers, and tasks in a manufactory, the system comprising:

a memory;

a plurality of input-output devices connected to the memory wherein data is transferred from the memory to the devices and from the devices to the memory;

input means for controlling the retrieving of schedule data including worker, work center, and task data from an input-output device and the storing of the schedule data in the memory;

first processing means for generating initial schedule data based on the schedule data stored in the memory wherein workers are assigned to work centers and tasks and for storing the initial schedule data in the memory;

second processing means for generating modified schedule data based on the initial schedule data stored in the memory wherein the start of at least two tasks are delayed when the delayed delivery cost of at least one end-product task is offset by the inventory carrying cost savings due to the delaying of the start of other tasks and for storing the modified schedule data in the memory; and

output means for transferring the modified schedule data from the memory to an input-output device to effect the allocation of the resources.

15. An apparatus for controlling the performing of tasks by workers at work centers in a manufactory, comprising;

a central processing unit;

a memory unit for storing data sent from the central processing unit and sending stored data to the central processing unit;

data input means for receiving data relating to each task including delayed delivery costs and inventory carrying costs, data relating to each work center, and data relating to each worker;

data storage means for storing the task, work center, and worker data received from the data input means in the memory unit;

first data processing means, working cooperatively with the central processing unit and the memory unit, for generating initial schedule data based on the task, work center, and worker data stored in the memory unit and for storing the initial schedule data in the memory unit;

second data processing means, working cooperatively with the central processing unit and the memory unit, for generating final schedule data based on the initial schedule data stored in the memory unit and for storing the final schedule data in the memory unit; and

data output means for retrieving the final schedule data from the memory unit and for outputting the final schedule data to effect the controlling of the performing of the tasks by the workers at the work centers.

16. A computer system for controlling the allocation of workers, tasks, and work centers in a manufactory, the system comprising:

a computer having a central processing unit, a memory, and input-output devices;

inputting means for inputting schedule and task data, including delayed delivery costs and inventory carrying costs, from an input-output device and for storing the schedule and task data in the memory;

generating means for generating initial schedule data, the generating means having means for retrieving the schedule and task data from the memory, means for processing the retrieved data in the central processing unit to generate initial schedule data wherein the workers are scheduled to perform tasks at work centers, and means for storing the initial schedule data in the memory;

enhancing means for enhancing the initial schedule data, the enhancing means having means for retrieving the initial schedule data from the memory, means for processing the retrieved data in the central processing unit to generate enhanced schedule data wherein the start of at least two tasks are delayed when the delayed delivery cost of at least one end-product task is offset by the inventory carrying cost savings due to delaying the start of the other tasks, and means for storing the enhanced schedule data in the memory; and

outputting means for outputting the enhanced schedule to an input-output device to effect the controlling of the allocation of the workers, work centers, and tasks.

17. A method for reallocating resources in a manufactory, the manufactory having a current allocation of resources, the resources including tasks, work centers, and workers, each task having an inventory carrying cost, the tasks including end-product tasks, each end-product task having a delayed delivery cost, the method comprising the steps of:

determining the current allocation of the resources in the manufactory;

monitoring the factory resources to determine when a resource becomes available;

when a resource becomes available, generating a new allocation of resources based on the delayed delivery costs and inventory carrying costs whereby the start of at least two tasks are delayed when the delayed delivery cost of at least one end-product task is offset by the inventory carrying cost savings due to delaying the start of other tasks; and

reallocating the resources based on the new allocation.

18. The method of claim 17 wherein the step of reallocating the resources includes the step of specifying the reallocated work center at which each worker is to work and the reallocated task that each worker is to perform.

19. A task and work center allocating apparatus for allocating tasks, and work centers among workers, the system comprising:

means for storing schedule and task information, delayed delivery costs, and inventory carrying costs;

means for generating an initial schedule based on the schedule and task information whereby workers are assigned to perform tasks at work centers;

means for modifying the initial schedule based on the delayed delivery costs and inventory carrying costs whereby the start of at least two tasks are delayed when the delayed delivery cost of at least one end-product task is offset by the inventory carrying cost savings due to delaying the start of other tasks; and

means for assigning a worker to perform a task at a work center in accordance with the modified initial schedule.