Method for allocating resources and processes for design and production plan scheduling

Abstract

A scheduling computer system optimizes the match between allocation of processes and resources. To do so, the system temporarily allocates the resources to a process selected based on the attributes of the resources and the processes, as well as the processing start and desired processing end times. In doing so, the system avoids selecting processes to which resources have been already allocated. The system also determines a resulting time value and a resulting fitness value based on the temporary allocation. Using the resulting time value and the resulting fitness value, the system determines the optimum resource for a particular process and allocates the resource to the process accordingly. The system also generates a scheduling chart illustrating the resource allocation.

Claims

What is claimed is:

1. A scheduling computer system for generating a scheduling chart, the computer system comprising:

resource defining means for inputting an attribute of each of a plurality of resources;

process defining means for inputting an attribute of each of a plurality of processes which are processed in a predefined sequence;

time setting means for inputting the processing start time and desired processing end time of each of said plurality of processes;

process selecting means for sequentially selecting a process, to which a resource is to be allocated, from said plurality of processes;

temporary allocating means for temporarily allocating each of said plurality of resources to the process selected by said process selecting means;

first evaluating means for evaluating the end time of a sequence of said plurality of processes by finding the end time of the sequence of said plurality of processes after said temporary allocation and for defining a resulting time evaluation value as the first criterion;

second evaluating means for evaluating the fitness of a resource for a process based on the attribute of the resource inputted by said resource defining means and on the attribute of the process inputted by said process defining means and for defining a resulting fitness evaluation value as the second criterion;

resource determining means for calculating an evaluation value for the combination of a process and a resource by evaluating said first criterion and second criterion for each of said plurality of resources and for determining the optimum resource for the process by comparing said evaluation values of all the resources;

process allocating means for sequentially allocating a resource determined by said resource determining means to a process selected by said process selecting means as a final result; and

means for generating the scheduling chart illustrating the process to which the resources have been allocated by the process allocating means,

wherein said process selecting means does not select processes to which resources have been already allocated by said process allocating means as objects of said temporary allocation.

2. A scheduling computer system as claimed in claim 1, wherein said time setting means sets the processing start time and desired processing end time of a sequence of said plurality of processes.

3. A scheduling computer system as claimed in claim 1, wherein said time setting means sets a processing start time and a desired processing end time of each of said plurality of processes.

4. A scheduling computer system as claimed in claim 1, further comprising first weight setting means for setting the first weight for weighting said resource with respect to the end time of said sequence of said plurality of processes, wherein said second evaluating means uses said first weight to evaluate the fitness of the corresponding resource for the corresponding process.

5. A scheduling computer system as claimed in claim 4, further comprising weight modifying means for modifying said first weight, set by said first weight setting means, according to a change of criteria in the evaluation criteria, when the criteria in at least one of a time evaluation value, created by said first evaluating means, and a fitness evaluation value, created by said second evaluating means, must be changed.

6. A scheduling computer system as claimed in claim 5, wherein said process selecting means calculates an evaluation value, based on the time relation among said plurality of processes, by using the earliest startable time and the allowable latest end time of each process and, based on this evaluation valued, selects a process.

7. A scheduling computer system as claimed in claim 1, wherein said process selecting means calculates an evaluation value, based on the time relation among said plurality of processes, by using the earliest processing start time and the allowable latest processing end time of each process and, based on this evaluation value, selects a process.

8. A scheduling computer system as claimed in claim 1, wherein said process selecting means calculates, based on the time relation among said plurality of processes, an evaluation value by generally evaluating the earliest processing start time and the allowable latest end time of each process as well as the correlation between the allocation status of each resource and each process at that time and, based on the evaluation value, selects a process.

9. A scheduling computer system as claimed in claim 8, further comprising second weight setting means for determining how high a priority is given to the corresponding process when determining said correlation between the allocation status of each resource and each process.

10. A scheduling computer system as claimed in claim 9, further comprising weight modifying means for modifying, when criteria for evaluating said correlation between the allocation status of each resource and each process must be changed, said second weight, set by said second weight setting means, according to a change in the criteria.

11. A scheduling computer system as claimed in claim 8, wherein said process selecting means selects a particular point in time between said earliest processing start time and said latest processing time based on said correlation between the status of each resource and each process at that time and determines the evaluation value as said evaluation value.

12. A scheduling computer system as claimed in claim 8, wherein said process selecting means calculates said evaluation value using the earliest start time and the allowable latest end time.

13. A scheduling computer system as claimed in claim 1, wherein said process defining means defines an additional resource for use in each process in addition to the resources defined by said resource defining means, and said second evaluating means increases the evaluation value of said fitness when two or more processes using said additional resource are allocated consecutively.

14. A scheduling computer system as claimed in claim 13, wherein said process selecting means calculates, based on the time relation among said plurality of processes, an evaluation value by generally evaluating the earliest processing start time and the allowable latest end time of each process as well as the correlation between the allocation status of each resource and each process at that time and, based on the evaluation value, selects a process.

15. A scheduling computer system as claimed in claim 14, wherein, when a process for which the same additional resources are defined as the those defined for this process is allocated to a resource at that time, said process selecting means evaluates highly said correlation between the allocation status of resources and each process.

16. A scheduling computer system as claimed in claim 14, wherein said process selecting means calculates said evaluation value using the earliest start time and the allowable latest end time.

17. A scheduling computer system as in one of claims 1 to 16, wherein said first evaluating means finds the first criterion by performing PERT (Program Evaluation and Review Technique) calculation.

18. A computer-implemented scheduling method for generating a scheduling chart, the method comprising:

a first step for inputting an attribute of each of a plurality of resources;

a second step for inputting an attribute of each of a plurality of processes which are processed in a predefined sequence;

a third step for inputting the processing start time and desired processing end time of each of said plurality of processes;

a fourth step for sequentially selecting a process to which a resource is to be allocated, from said plurality of processes;

a fifth step for temporarily allocating each of said plurality of resources to the process selected in said fourth step;

a sixth step for evaluating the end time of a sequence of said plurality of processes by finding the end time of the sequence of said plurality of processes after said temporary allocation and for defining a resulting time evaluation value as the first criterion;

a seventh step for evaluating the fitness of a resource for a process based on the attribute of the resource inputted in said first step and on the attribute of the process inputted in said second step and for defining a resulting fitness evaluation value as the second criterion;

an eighth step for calculating an evaluation value for the combination of a process and a resource by evaluating said first criterion and second criterion for each of said plurality of resources and for determining the optimum resource for the process by comparing said evaluation values of all the resources;

a ninth step for sequentially allocating a resource determined in said eight step to a process selected in said fourth step as a final result; and

a tenth step for generating the scheduling chart illustrating the processes to which the resources have been allocated,

wherein, in said fourth step, processes to which resources have been already allocated in said ninth step are not selected.

19. A computer-implemented scheduling method as claimed in claim 18, further comprising an eleventh step for setting the first weight for weighting said resource, with respect to the end time of said sequence of said plurality of processes, wherein, in said seventh step, said first weight is used to evaluate the fitness of the corresponding resource for the corresponding process.

20. A computer-implemented scheduling method as claimed in claim 19, further comprising a twelfth step for modifying said first weight, set by said eleventh step, according to a change of criteria in the evaluation criteria, when the criteria in at least one of a time evaluation value, created by said sixth step, and a fitness evaluation value, created by said seventh step, must be changed.

21. A computer-implemented scheduling method as claimed in claim 18, wherein said fourth step calculates, based on the time relation among said plurality of processes, an evaluation value by using the earliest processing start time and the allowable latest processing time of each process and, based on this evaluation value, selects a process.

22. A computer-implemented scheduling method as claimed in claim 18, wherein said fourth step calculates, based on the time relation among said plurality of processes, an evaluation value by evaluating the earliest end start time and the allowable latest processing time of each process as well as the correlation between the allocation status of each resource and each process at that time and, based on the evaluation value, selects a process.

23. A computer-implemented scheduling method as claimed in claim 22, further comprising a thirteenth step for determining how high a priority is given to the corresponding process when determining said correlation between the allocation status of each resource and each process.

24. A computer-implemented scheduling method as claimed in claim 18, wherein said second step defines an additional resource for use in each process in addition to the resources defined by said first step, and said seventh step increases the evaluation value of said fitness when two or more processes using said additional resource are allocated consecutively.

25. A computer-implemented scheduling method as claimed in claim 24, wherein said fourth step calculates, based on the time relation among said plurality of processes, an evaluation value by generally evaluating the earliest processing start time and the allowable latest end time of each process as well as the correlation between the allocation status of each resource and each process at that time and, based on the evaluation value, selects a process.

26. A computer-implemented scheduling method as in one of claims 18 to 25, wherein said sixth step finds the first criterion by performing PERT (Program Evaluation and Review Technique) calculation.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to a scheduling device and method which help create many types of schedules such as those for the development or design projects of various applications or for the production management in plants or other places.

2. Description of the Prior Art

In the development or design projects in many applications or in the production management in plants or other places, scheduling problems have been major issues in plan-applications or plan-making operations. This scheduling problem is defined generally as "a problem which allocates resources and time, required for process execution, to a given job."

In the following discussion, the scheduling problem refers to "who" will do "what job" and "when." And, "what job" is called a "process", "who" is called a "resource", and "when" means a time to perform a process.

There are many scheduling application in various fields. The following focuses on the prior art of project scheduling in two fields: project scheduling and production-plan scheduling. Project scheduling requires the understanding of process sequence because it is complex. On the other hand, production-plan scheduling must take into consideration many restrictions such as those on the facilities or setup times.

To cope with these problems, the prior art uses the following method:

1. Project scheduling

In project scheduling, study has been made traditionally on PERT and CPM (Tomoaki Sekine, PERT CPM. Nikka-girenn). PERT forms a process network that reflects the process sequence and, based on this network, calculates the earliest start time and the latest end time. PERT gives information on the spare time of each process, etc. CPM allows reduction of work time based on the result of PERT. CPM is not explained here because it is not a technique for resource allocation.

Normally, PERT is used with the "resource leveling" method in many papers, "resource leveling" is also called "resource allocation". We define "resource leveling" as performing alternative resource selection in this specification in order to distinguish from general "resource leveling" or "resource allocation". This resource leveling method temporarily determines the work time of each process according to the result of PERT calculation and, when the schedule is found to be impractical under some resource restrictions, sequentially moves processes allocated to a busy time to another period of time.

However, this resource leveling method, which sequentially moves process times considering resource priority or spare times, is used basically for a single resource whose capacity is limited. In project scheduling, for example, a single resource means that a job is allocated to a group (project team), not to individuals. In this case, the capacity is the maximum number of people of a group.

Another known scheduling method for a plurality of resources is RAMPS (Resource Allocation and Multi-Project Scheduling: Refer to the book above). This method, which uses a plural resources such as an "electrical designer group" and "mechanical designer group", creates a schedule using data on the number of designers required for each process. It allows us to create a schedule for a plural resources.

2. Production-plan scheduling

In production-plan scheduling, the schedule unit depends on the production method. That is, in the large variety, small-lot-sized production, the schedule unit is a production process of each order; in the mass production, the schedule unit is a production process of one of lots of a product type. The problem of production-plan scheduling is similar to that of project scheduling in that there are many processes. That is, it is necessary to consider a complex process sequence while considering resource priority and resource ability and to make a schedule. A scheduling method like this is found, for example, in Japanese Non-examined Patent Publication No. 6-35920.

However, in many cases, production-plan scheduling is more complex. For example, we must take into considerations the following restrictions: each process may require two resources, for example a machine and a jig, at the same time, or the one-hour setup time may be required when the same machine processes two or more lots continuously using different jigs. In the mass production, there are sometimes too many lots to be scheduled in one process.

To solve these problems, the following scheduling methods are used. One method is to determine the earliest start time and latest end time of each process based on an estimate of how busy the process will be and how long, including a wait time, it will take to complete and to schedule a process independently so that it ends within the specified latest end time. Another method is to schedule in process sequence; in this case, the end time of a process is used as the start time of the following process. In this method, scheduling is done for single process at a time. Or, even if scheduling is done for some sequence of processes, it is very simple.

Now, consider a scheduling method which takes a setup time into consideration. Also consider that there is the following restriction: "Some processes require a machine as well as a jig, and some products may use the same jig. In this case, exchanging jigs on a machine requires a setup time." Suppose that there are enough jigs. Then, grouping lots using the same jig decreases the setup time and increases the machine efficiency.

However, the whole project may be tardy because a lot, if too large, increases the lot process time but also delays the processing of other lots. This means that two contradicting objects--to increase machine efficiency and to reduce the lot process time--must be considered.

Conventional production-plan scheduling methods to solve this problem include an OR (Operations Research) method, such as the branch-and-bound method or integer programming method, and an expert system which describes a dispatching rule using the IF-THEN rule.

An OR method evaluates a schedule which is the final result. For example, in the above example, this method calculates, for the final scheduling result, the first evaluation criterion which is the sum of working ratios of all machines and the second evaluation criterion which is the sum of project times. In an OR field, the above problem is usually treated as a lot sequencing problem, and many studies have been made on a method to optimize this sequencing. In most cases, a given initial solution is modified to make it an optimum solution.

An expert system method, on the other hand, stores the heuristic knowledge of experienced planners in a knowledge database on the computer for use in simulation on. This method, similar to a procedure a human being uses to schedule, repeatedly selects unallocated processes for allocation. Selection and allocation performed during scheduling are called dispatching, and selection and allocation rules are called dispatching rules. In the AI (Artificial Intelligence) field, scheduling is performed through inference using the IF-THEN rules, which are represented in the following form:

IF-THEN

This rule consists of the IF (condition part) statement and the THEN (conclusion part) statement.

Consider a problem to reduce a setup time. In this example, let the end time of the latest process which each resource is allocated be the end time of the resource, and let the jig used by the process be called the current jig. In this case, allocation is performed according to the following rules:

IF

a jig to be used by a process is the current jig of a resource

THEN

the resource is allocated to the process

IF

there is no process which uses a jig used by each resource currently

THEN

the process whose required time is earliest is allocated to the resource whose end time is earliest.

This rule-form representation allows us to build a scheduling system easier. In many of scheduling systems currently available, dispatching rules are coded in the IF-THEN rules or some other programming statements. This rule-form scheduling is characterized in that a practical scheduling system may be built without having to find the optimum solution. Because of a reduced amount of calculation compared with that of an OR method, this scheduling method may be applied to a system where there are many machines or priorities are assigned to machines.

A scheduling system using the dispatching rules described above is described in `HEURISTIC SCHEDULING SYSTEMS Chapter 12, "SHOP ROUTING"; MORTON et al.; 1993.`

PROBLEMS TO BE SOLVED BY THE INVENTION

Conventional scheduling methods have the following problems:

1. Project scheduling

Conventional project scheduling is used to create a schedule considering the capacity of a group, because it is used primarily for construction sites and the like. However, in the case of design work, it is necessary to make a schedule considering the individual designer's ability because the work time depends largely on individual designer's ability and there are works on which some designers cannot work. In a situation where a resource is allocated uniquely to a process, individual designers are allocated to work. In this case, a schedule is made using the resource leveling method with a plurality of resources set up.

Normally, only one person is not always allocated to a specific work; instead, one of many persons is selected. In a situation where there are a plurality of allocatable resources for each process, changing resources changes the load status and, there are a lot of number of combinations of processes and allocatable resources. For example, assume that there are 10 processes to be scheduled and that there are three alternative resources for each allocatable resource. Then, there are a total of about 170,000 resource patterns selectable for each process. It is impossible to resolve if we have to consider all these patterns. However, in reality, there are usually some priority relations; for example, a resource to be selected as much as possible is sometimes not available, and another resource is used for it.

For example, in the above design work, a chief designer, who is assigned to each design item, should work on it as much as possible. However, if we adhere to the restriction that a chief designer should work on the design item, the whole project is delayed. In this case, it is necessary to allocate the design item to the chief designer and then, considering the whole project time, to do resource leveling by moving the process to other resources. However, this leveling method is rather complex. In the conventional leveling method, only the period of time should be considered so that the project completes on or before the completion date. This method requires us to consider, when leveling, not only the period of time but also allocatable resources.

As described above, it is difficult, with the use of the conventional resource leveling method or its extended method, to make a schedule for a problem whose sequence relation is complex while considering both the time factor and the priority of each of a plurality of resources.

2. Production-plan scheduling

When optimizing the sequencing problem with the use of the above-described OR method, a schedule may be created for single machine, but not for a plurality of machines. For a plurality of machines, the method may be applied only to two or three machines. In most cases, a study is being made, not on a plurality of processes, but on a single process.

This OR method is advantageous in that it gives us an optimum solution and its object is clear, because it represents a scheduling target with the use of an evaluation function for the final result. However, its solution method is complex and cannot be applied to complex problems because of restrictions on calculation times.

With the rule-form representation of the expert system method which is used to specify a condition for a process that is allocated, it is difficult to describe a set of rules for the optimum solution which takes into consideration the machine working ratios or lot process times. An attempt to describe detailed conditions also makes the rule set complex and makes it difficult to build a system. In addition, the expert system method makes it difficult to fine-tune the knowledge to reflect some specific conditions, such as a process relation, a limit on the time delay, or an error in some machines. Because the knowledge structure becomes more complex, it is difficult to build a system which changes its behavior to adapt to data which change day by day.

This invention seeks to solve the problems associated with the prior art described above. It is an object of this invention to provide a scheduling system and a scheduling method which can evaluate the fitness of each of a plurality of fixed-sequenced processes for each alternative resources, evaluate the time factor of processes, and optimize the balance between the fitness and the time factor.

It is another object of this invention to provide a scheduling system and a scheduling method which can optimize the balance between the setup time and the time factor of the processes when allocating a plurality of types of resources to a plurality of processes.

It is still another object of this invention to provide a scheduling system and a scheduling method which can adjust the balance between the fitness and the time factor and the balance between the setup time and the time factor.

SUMMARY OF THE INVENTION

To achieve the above objects, a scheduling system according to claim 1 comprises: resource defining means for defining the attribute, such as an ability, of each of the plurality of resources; process defining means for defining the attribute of each of a plurality of processes which are processed in a predefined sequence; time setting means for setting the processing startable time and desired processing time of a plurality of processes; process selecting means for sequentially selecting a process, to which a resource is to be allocated, from the plurality of processes; temporary allocating means for temporarily allocating a process, selected by the process selecting means, to each of the plurality of resources; first evaluating means for evaluating the end time of a sequence of processes with respect to the desired end time of the corresponding sequence of processes, set by the time setting means, by finding the end time of the sequence of the plurality of processes after the temporary allocation and for defining a resulting time evaluation value as the first criterion; second evaluating means for evaluating the fitness of a resource for a process based on the attribute of the resource and on the attribute of the process and for defining a resulting fitness evaluation value as the second criterion; resource determining means for calculating an evaluation value for the combination of a process and a resource by evaluating both of the first criterion and the second criterion and for determining, based on the evaluation value, the best resource for the process; and process allocating means for allocating a process, selected by the process selecting means, to a resource determined by the resource determining means.

An invention according to claim 18 is a method for the invention as claimed in claim 1. That is, this invention is a scheduling method comprising: a first step for defining the attribute, such as an ability, of each of a plurality of resources; a second step for defining the attribute of each of a plurality of processes which are processed in a predefined sequence; a third step for setting the processing startable time and desired processing time of the plurality of processes; a fourth step for sequentially selecting a process, which is to be allocated to a resource, from the plurality of processes; a fifth step for temporarily allocating a process, selected by the fourth step, to each of the plurality of resources; a sixth step for evaluating the end time of a sequence of processes with respect to the desired end time of the corresponding sequence of processes, set by the third step, by finding the end time of the sequence of the plurality of processes after the temporary allocation and for defining a resulting time evaluation value as the first criterion; a seventh step for evaluating the fitness of a resource for a process based on the attribute of the resource and on the attribute of the process and for defining a resulting fitness evaluation value as the second criterion; an eighth step for calculating an evaluation value for the combination of a process and a resource by evaluating both of the first criterion and the second criterion and for determining, based on the evaluation value, the best resource for the process; and a ninth step for sequentially allocating a process, selected by the step fourth, to a resource determined by the step eighth.

According to the inventions as claimed in claims 1 and 18, each of alternative resources is allocated to any of a plurality of processes. In this case, it is assumed that each combination of a process and a resource has its own level of fitness. More specifically, this level of fitness determines at what process each resource is good or how well each process is processed by each resource. Various factors such as efficiency depend on a process to which each resource is allocated. On the other hand, allocation based only on the fitness may cause a tardy schedule.

To solve this problem, this invention temporarily allocates a process to each resource and finds the end time of each subsequent process, especially the end time of a sequence of consecutive processes, to evaluate the desired processing time which is the desired end time. This time evaluation, represented as a numeric value, is used as the first criterion, and the fitness, represented as a numeric value, is used as the second criterion. The invention evaluates the first criterion and the second criterion to determine the best combination of processes and resources.

Evaluating the fitness of each process for each resource while considering the time factor allows the user to make a schedule which well balances the fitness and the time factor.

A scheduling system according to claim 2 is a scheduling system as claimed in claim 1, wherein the time setting means sets the processing startable time and desired processing time of a sequence of the plural processes.

According to the invention as claimed in claim 2, because the processing startable time and desired processing time are set for a sequence of a plurality of processes, time data entry becomes easy.

A scheduling system according to claim 3 is a scheduling system as claimed in claim 1, wherein the time setting means sets a processing startable time and a desired processing end time of each of plural of processes.

According to the invention as claimed in claim 3, a processing startable time and a desired processing time may be set for each process of a sequence of a plurality of processes.

A scheduling system according to claim 4 is a scheduling system as claimed in claim 1, further comprising first weight setting means for setting the first weight for determining a balance in the evaluation between the first criterion and the second criterion, wherein the resource determining means uses the first weight when evaluating the first criterion and second criterion.

An invention according to claim 19 is a method for the invention as claimed in claim 4. That is, this is a scheduling method as claimed in claim 18, further comprising a tenth step or setting the first weight for determining a balance in the evaluation between the first criterion and the second criterion, wherein the step eighth uses the first weight when evaluating the first criterion and second criterion.

According to the inventions as claimed in claims 4 and 19, the first weight is considered when evaluating the fitness of processes for resources to balance the first criterion and the second criterion. This determines the best combination of processes and resources.

A scheduling system according to claim 5 is a scheduling system as claimed in claim 4, further comprising weight modifying means for modifying the first weight, set by the first weight setting means, according to a change of criteria in the evaluation criteria, when the criteria in at least one of a time evaluation value, created by the first evaluating means, and a fitness evaluation value, created by the second evaluating means, must be changed.

An invention according to claim 20 is a method for the invention as claimed in claim 5. That is, this is a scheduling method as claimed in claim 19, further comprising a eleventh step for modifying the first weight, set by the tenth step, according to a change of criteria in the evaluation criteria, when the criteria in at least one of a time evaluation value, created by the sixth step, and a fitness evaluation value, created by the seventh step, must be changed.

According to the inventions as claimed in claims 5 and 20, the first weight is modified according to the relation between processes, a limit on the time delay, and a failure in a specific resource. This makes it possible to create a flexible schedule.

A scheduling system according to claim 6 is a scheduling system as claimed in claim 5, wherein the process selecting means calculates the evaluation value using the earliest start time and the allowable latest end time.

According to the invention as claimed in claim 6, the operation becomes simple because the earliest start time is used as the earliest processing start time and because the latest end time is used as the allowable latest processing time.

A scheduling system according to claim 7 is a scheduling system as claimed in claim 1, wherein the process selecting means calculates an evaluation value, based on the time relation among the plurality of processes, by using the earliest processing start time and the allowable latest processing time of each process and, based on this evaluation value, selects a process.

An invention according to claim 21 is a method for the invention as claimed in claim 7. That is, this is a scheduling method as claimed in claim 18, wherein the fourth step calculates, based on the time relation among the plurality of processes, an evaluation value by using the earliest processing start time and the allowable latest processing time of each process and, based on this evaluation value, selects a process.

According to the inventions as claimed in claims 7 and 21, the earliest processing start time and the allowable latest processing time of each process is evaluated, based on the time relation among a plurality of processes, to select a process. This enables a high priority process with an earlier start time and end time to be selected first.

A scheduling system according to claim 8 is a scheduling system as claimed in claim 1, wherein the process selecting means calculates, based on the time relation among the plurality of processes, an evaluation value by generally evaluating the earliest processing start time and the allowable latest processing time of each process as well as the correlation between the allocation status of each resource and each process at that time and, based on the evaluation value, selects a process.

An invention according to claim 22 is a method for the invention as claimed in claim 8. That is, this is a scheduling method as claimed in claim 18, wherein the fourth step calculates, based on the time relation among the plurality of processes, an evaluation value by generally evaluating the earliest processing start time and the allowable latest processing time of each process as well as the correlation between the allocation status of each resource and each process at that time and, based on the evaluation value, selects a process.

According to the inventions as claimed in claims 8 and 22, an evaluation value is calculated, based on the time relation among a plurality of processes, by generally evaluating the earliest processing start time and the allowable latest processing time of each process as well as the correlation between the allocation status of each resource and each process at that time. This enables the user to select a high priority process with an earlier start time and end time while referring to the allocation status of each resource at that time.

A scheduling system according to claim 9 is a scheduling system as claimed in claim 8, further comprising second weight setting means for determining the correlation between the allocation status of each resource and each process.

A scheduling system according to claim 23 is a scheduling system as claimed in claim 22, further comprising a twelfth step for determining said correlation between the allocation status of each resource and each process.

According to the invention as claimed in claim 9 and 23, the second weight determines the correlation between the allocation status of each resource and each process. This allows the user to determine the correlation according to the status at the time, allowing him to select a process suitable to the status.

A scheduling system according to claim 10 is a scheduling system as claimed in claim 9, further comprising weight modifying means for modifying, when criteria for evaluating the correlation between the allocation status of each resource and each process must be changed, the second weight, set by the second weight setting means, according to a change in the criteria.

According to the invention as claimed in claim 10, a flexible schedule is created by modifying the second weight according to specific conditions, such as the relation between processes, a limit on the time delay, or a failure in a specific resource.

A scheduling system according to claim 11 is a scheduling system as claimed in claim 8, wherein the process selecting means selects a particular point in time between the earliest processing start time and the latest processing time based on the correlation between the status of each resource and each process at that time and determines the evaluation value as the evaluation value.

According to the invention as claimed in claim 11, an evaluation value is calculated based on the correlation between the resource allocation status and each process at that time and on the second weight. This allows the user to select a process suitable for the status.

A scheduling system according to claim 12 is a scheduling system as claimed in claim 8, wherein the process selecting means calculates the evaluation value using the earliest start time and the allowable latest end time.

According to the invention as claimed in claim 12, the operation becomes simple because the earliest start time is used as the earliest processing start time and because the latest end time is used as the allowable latest processing time.

A scheduling system according to claim 13 is a scheduling system as claimed in claim 1, wherein the process defining means defines an additional resource for use in each process in addition to the resources defined by the resource defining means, and the second evaluating means increases the evaluation value of the fitness when two or more processes using the additional resource are allocated consecutively.

An invention according to claim 24 is a method for the invention as claimed in claim 13. That is, this is a scheduling method as claimed in claim 18, wherein the second step defines an additional resource for use in each process in addition to the resources defined by the first step, and the seventh step increases the evaluation value of the fitness when two or more processes using the additional resource are allocated consecutively.

According to the inventions as claimed in claims 13 and 24, a well-balanced, optimum schedule is created as follows. Assume that processes are allocated to resources when an additional resource, for example a jig, is defined for each of a plurality of processes. In this case, when a plurality of different continuous processes, each using a different type of additional resource, are processed, the time for exchanging additional resources (hereafter called setup time) is necessary between processes. This means that a reduction in the setup time increases the efficiency of resources. However, an attempt to reduce this setup time sometimes causes a specific type of process to be expedited and other processes to be delayed. This may cause a specified number of processes to end behind the schedule.

So, when allocating a selected process to a resource, a check is made to see whether or not the additional resource defined for this process matches that defined for the process allocated last to the resource. This evaluation is used as the second criterion. If two continuous processes allocated to the same resource use the same additional resource, no setup time is necessary.

The end time of each subsequent process, especially the end time of a sequence of subsequent processes, is calculated for the combination of the process and the resource in order to perform time evaluation for the desired end time. This time evaluation, represented as a numeric value, is used as the first criterion.

Evaluation of both the time factor and the setup time ensures the best scheduling where the resource efficiency and the time factor are well balanced.

A scheduling system according to claim 14 is a scheduling system as claimed in claim 13, wherein the process selecting means calculates, base on the time relation among said plurality of processes, an evaluation value by generally evaluating the earliest processing time of each process as well as the correlation between the allocation status of each resource and each process that time and, based on the evaluation value, selects a process.

An invention according to claim 25 is a method for the invention as claimed in claim 14. That is, this is a scheduling method as claimed in claim 24, wherein the fourth step calculates, based on the time relation among the plurality of processes, an evaluation value by generally evaluating the earliest processing start time and the allowable latest processing time of each process as well as the correlation between the allocation status of each resource and each process at that time and, based on the evaluation value, selects a process.

According to the inventions as claimed in claims 14 and 25, an evaluation value is calculated, based on the time relation among a plurality of processes, by generally evaluating the earliest processing start time and the allowable latest processing time of each process as well as the correlation between the allocation status of each resource and each process at that time. This enables the user to select a high priority process with an earlier start time and end time while referring to the allocation status of each resource at that time.

A scheduling system according to claim 15 is a scheduling system as claimed in claim 14, wherein, when a process for which the same additional resources as the those defined for this process is allocated to a resource at that time, the process selecting means evaluates highly the correlation between the allocation status of resources and each process.

According to the invention as claimed in claim 15, a process with the same additional resource are defined as that of the process allocated to that resource at that moment is selected with priority.

A scheduling system according to claim 16 is a scheduling system as claimed in claim 14, wherein the process selecting means calculates the evaluation value using the earliest start time and the allowable latest end time.

According to the invention as claimed in claim 16, the operation becomes simple because the earliest start time is used as the earliest processing start time and because the latest end time is used as the allowable latest processing time.

A scheduling system according to claim 17 is a scheduling system as in one of claims 1 to 16, wherein the first evaluating means finds the first criterion by performing PERT (Program Evaluation and Review Technique) calculation.

An invention according to claim 26 is a method for the invention as claimed in claim 17. That is, this is a scheduling method as in one of claims 18 to 25, wherein the sixth step finds the first criterion by performing PERT (Program Evaluation and Review Technique) calculation.

According to the inventions as claimed in claims 17 and 26, the PERT calculation is executed to perform time evaluation each time a resource is allocated to a process. This eliminates the need for reallocation, thus reducing the scheduling time. More specifically, the PERT calculation is performed to evaluate the time. That is, the PERT calculation creates a process network representing the time relation such as the sequence or parallel relation of processes. And, when one or more processes are allocated to a resource or some period of time, the start times of other related processes or end times of other processes are obtained. Time data used in this invention may be calculated by any other method, with different names or different process forms, as long as the same type of calculation is performed.

Other and further objects, features and advantages of the invention will appear more fully from the following description.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a functional block diagram showing the configuration of the scheduling system used in the first and second embodiments of this invention.

FIG. 2 is a flowchart showing an example of scheduling procedures used in the first and second embodiments of this invention.

FIG. 3 is a diagram showing, in a network form, the sequence relation of the processes used in the first embodiment of this invention.

FIG. 4 is a diagram showing the result of the PERT calculation based on the sequence relation of the processes used in the first embodiment of this invention.

FIG. 5 is a Gantt chart showing the result of scheduling in the first embodiment of this invention, which shows the schedule for each design item.

FIG. 6 is a Gantt chart showing the result of scheduling in the first embodiment of this invention, which shows the schedule for each designer.

FIG. 7 is a Gantt chart which is continued from the schedule in FIG. 6.

FIG. 8 is a Gantt chart which is continued from the schedule in FIG. 7.

FIG. 9 is a Gantt chart which is continued from the schedule in FIG. 8.

FIG. 10 is a Gantt chart showing the result of scheduling in the second embodiment of this invention, which shows the schedule for each machine.

FIG. 11 is a Gantt chart showing the result of scheduling in the second embodiment of this invention, which shows the schedule for each process.

FIG. 12 is a Gantt chart showing the result of an example of scheduling to reduce the production amount as a whole in the second embodiment of this invention, which shows the schedule for each machine.

FIG. 13 is a Gantt chart showing the result of an example of scheduling to reduce the production amount as a whole in the second embodiment of this invention, which shows the schedule for each process.

SUMMARY OF THE INVENTION

To achieve the above objects, one aspect of the present invention is a scheduling computer system for generating a schedule chart, the computer system comprising: resource defining means for inputting the attribute, such as an ability, of each of a plurality of resources; process defining means for inputting the attribute of each of a plurality of processes which are processed in a predefined sequence; time setting means for inputting the processing startable time and desired processing end time of said plurality of processes; process selecting means for sequentially selecting a process, to which a resource is to be allocated, from said plurality of processes; temporary allocating means for temporarily allocating each of said plurality of resources to a process selected by said process selecting means; first evaluating means for evaluating the end time of a sequence of processes with respect to the desired end time of said desired processing end time of the corresponding sequence of processes, set by said time setting means, by finding the end time of the sequence of said plurality of processes after said temporary allocation and for defining a resulting time evaluation value as the first criterion; second evaluating means for evaluating the fitness of a resource for a process based on the attribute of the resource inputted by said resource defining means and on the attribute of the process inputted by said process defining means and for defining a resulting fitness evaluation value as the second criterion; resource determining means for calculating a general evaluation value for the combination of a process and a resource by evaluating generally said first criterion and second criterion for each of said plurality of resources and for determining the optimum resource for the process by comparing said general evaluation values of all the resources; process allocating means for sequentially allocating a resource determined by said resource determining means to a process selected by said process selecting means as a final result; and means for generating a scheduling chart illustrating the process to which the resources have been allocated by the process allocating means, wherein said process selecting means does not select processes to which resources have been already allocated by said process allocating means as objects of said temporary allocation, and said first evaluating means respects said processes to which resources have been already allocated by said process allocating means when evaluating time.

Another aspect of the present invention is a computer-implemented scheduling method for generating a scheduling chart, comprising: a first step for inputting the attribute, such as an ability, of each of a plurality of resources; a second step for inputting the attribute of each of a plurality of processes which are processed in a predefined sequence; a third step for inputting the processing startable time and desired processing end time of said plurality of processes; a fourth step for sequentially selecting a process, to which a resource is to be allocated, from said plurality of processes; a fifth step for temporarily allocating each of said plurality of resources to a process selected in said fourth step; a sixth step for evaluating the end time of a sequence of processes with respect to the desired end time of said desired processing end time of the corresponding sequence of processes, set by said third step, by finding the end time of the sequence of said plurality of processes after said temporary allocation and for defining a resulting time evaluation value as the first criterion; a seventh step for evaluating the fitness of a resource for a process based on the attribute of the resource inputted in said first step and on the attribute of the process inputted in said second step and for defining a resulting fitness evaluation value as the second criterion; an eighth step for calculating a general evaluation value for the combination of a process and a resource by evaluating generally said first criterion and second criterion for each of said plurality of resources and for determining the optimum resource for the process by comparing said general evaluation values of all the resources; a ninth step for sequentially allocating a resource determined in said eighth step to a process selected in said fourth step as a final result; and a tenth step for generating a scheduling chart illustrating the processes to which the resources have been allocated, wherein, in said fourth step, processes to which resources have been already allocated in said ninth step are not selected, and, in said seventh step, said processes to which resources have been already allocated in said ninth step are also respected when evaluating time.

According to the invention, any of a plurality of processes is allocated to each of alternative resources during scheduling. In this case, it is assumed that each combination of a process and a resource has its own level of fitness. More specifically, this level of fitness determines at what process each resource is good or how well each process is processed by each resource. Various factors such as efficiency depend on a process to which each resource is allocated. On the other hand, allocation based only on the fitness may cause a tardy schedule.

To solve this problem, this invention temporarily allocates a resource to each process and finds the end time of each subsequent process, especially the end time of a sequence of consecutive processes, to evaluate the desired processing end time. This time evaluation represented as a numeric value, is used as the first criterion, and the fitness, represented as a numeric value, is used as the second criterion. The invention evaluates first criterion and the second criterion to determine the best combination of processes and resources.

Evaluating the fitness of each process for each resource while considering the time factor allows the user to make a schedule that well balances the fitness and the time factor.

DETAILED DESCRIPTION

A. First Embodiment

(A-1) Configuration of the First Embodiment

FIG. 1 is a block diagram showing the configuration of the scheduling system according to the first embodiment of this invention. In this figure, the process defining means 1 groups a plurality of processes into some process groups and, for each process group, defines attributes of the process; those attributes include information such as a standard work time and resource preferences. The sequence relation defining means 2 defines the sequence relation of the processes. The sequence relation defining means 2 may be any method capable of defining the sequence relation of the processes; for example, it may use a graphical user interface.

The resource defining means 3 defines a plurality of resources and, for each resource, defines its attributes such as the capabilities of the resource in relation to a process. The start/end time setting means 4 sets the earliest possible start time and the desired end time for a group of processes defined by the process defining means 1 described above. The contents defined by the process defining means 1 and the sequence relation defining means 2 as well as the contents set up by the start/end time setting means 4 are stored in the process data 5a, and the contents defined by the resource defining means 3 are stored in the resource data 5b.

The process selecting means 10 performs the PERT calculation to select higher-priority processes defined by the process defining means 1. The temporary allocating means 7 performs PERT calculation to temporarily allocate to each process the resource selected by the process selecting means 10.

The first evaluating means 9a evaluates allocation times based on the PERT calculation performed by the temporary allocating means 7. The second evaluating means 9b evaluates selected resources. And, based on the evaluation of the first evaluating means 9a and that of the second evaluating means 9b, the resource determining means 8 evaluates the combination of each process, selected by the process selecting means 10, and each resource, and selects the resource that is best for the process.

The process allocating means 6 allocates the resources, determined by the resource determining means 8, to each of a plurality of processes.

The first weight setting means 11a sets the first weight when the second evaluating means 9b performs evaluation. The second weight setting means 11b sets the second weight when the process selecting means 10 selects a process. The weight modifying means 12 modifies the first and second weights according to various conditions such as specific relations of processes, the maximum allowable delays, or some failing resources.

(A-2) Operation of the First Embodiment

(1) How is a project scheduled in the first embodiment?

The following explains an example of project scheduling using a scheduling system with the configuration described above.

In the following discussion, the design project of a video cassette recorder is used as an example of project scheduling problem. In this embodiment, a project is scheduled by allocating resources which are workers (in this example, designers) to processes. They are responsible for designing two types of video cassette recorder, each of which has its own schedule. That is, the designer team is responsible for designing two types of model, each with its own project start date and desired project end date. The design of each model consists of a plurality of design items, each of which consists of a plurality of processes. And, a chief designer is assigned to each design item. Under this condition, this problem determines the designers and work days for all the processes.

The scheduling of this project is evaluated based on the following two criteria:

1. The chief designer responsible for each design item should work as much time on the design item as possible.

2. The project should be scheduled so that the desired project end date requirements are satisfied as much as possible.

That is, the scheduling problem in this embodiment requires that a schedule be made while well balancing the above two evaluation criteria.

(2) Entering scheduling targets and associated data

The user enters data on a plurality of processes, which are scheduling targets, and on a plurality of resources as follows:

First, the user uses the process defining means 1, the sequence relation defining means 2, and the resource defining means 3, which are shown in FIG. 1, to enter data on the processes, sequence relation, available resources, and standard manpower. The sequence relation of processes may be calculated within the system using data defined by the process defining means 1 or some other data.

Basically, each model consists of three components: mechanical part (1), circuit part (2), and cabinet (3). The mechanical part, in turn, consists of the loading mechanism (1-1), head (1-2), and winder (1-3); the circuit part consists of the mechanical part driver (2-1), image signal processor (2-2), and power supply (2-3); and the cabinet consists of the cabinet itself (3-1). Each of these items is designed, in most cases, in four processes: concept design (1), specifications preparation (2), internal design (3), and parts diagram preparation (4).

First, the user uses the process defining means 1 to enter the standard number of days for each of the above processes. As a result, the standard manpower table, shown in Table 1, is created.

                  TABLE 1
    ______________________________________
                                           Parts
                     Concept Specification
                                     Internal
                                           diagram
    ID   Item name   design  preparation
                                     design
                                           preparation
    ______________________________________
    11   Mechanical part
    11-1 Loading     8       6       21    6
         mechanism
    11-2 Head        4       8       21    4
    11-3 Winder      6       6       21    4
    12   Circuit part
    12-1 Mechanical part
                     8       10      25    6
         driver
    12-2 Image signal
                     6       10      10    4
         processor
    12-3 Power supply
                     6       6       10    4
    13   Cabinet
    13-1 Cabinet     4       4        6    4
    ______________________________________

                  TABLE 2
    ______________________________________
    ID         Item name   Chief designer
    ______________________________________
    1          Mechanical part
                           A
    2          Circuit part
                           B
    3          Cabinet     C
    ______________________________________

                  TABLE 3
    ______________________________________
    Predecessor
              Successor    Predecessor
                                     Successor
    process   process      process   process
    ______________________________________
    11-1-1    12-1-1       21-1-1    22-1-1
    11-2-1    12-1-1       22-1-1    22-1-1
    11-3-1    12-1-1       21-1-1    22-1-1
    12-1-2    12-3-1       21-1-1    22-1-1
    12-2-2    12-3-1       22-2-2    22-3-1
    11-1-3    13-1-1       21-1-3    23-1-1
    11-2-3    13-1-1       21-2-3    23-1-1
    11-3-3    13-1-1       21-3-3    23-1-1
    12-1-3    13-1-1       22-1-3    23-1-1
    12-2-3    13-1-1       22-2-3    23-1-1
    12-2-3    13-1-1       22-2-3    23-1-1
    ______________________________________

                  TABLE 4
    ______________________________________
             Concept Specification      Parts diagram
    Designer name
             design  preparation
                               Internal design
                                        preparation
    ______________________________________
    Mechanical part/Cabinet (mechanical design)
    A        1.0     1.0       1.0      1.0
    B        1.0     1.0       1.0      1.0
    C        1.0     1.0       1.0      1.0
    D        x       1.0       1.0      1.0
    E        x       x         x        x
    F        x       0.8       0.8      0.8
    Circuit part (electrical design)
    A        1.0     1.0       1.0      1.0
    B        1.0     1.0       1.0      1.0
    C        1.0     1.0       1.0      1.0
    D        x       x         x        x
    E        x       1.0       1.0      1.0
    F        x       0.8       0.8      0.8
    ______________________________________

                  TABLE 5
    ______________________________________
    Medel       Earliest start date
                            Desired end date
    ______________________________________
    1           1994/4/1    1994/7/1
    2           1994/6/1    1994/10/1
    ______________________________________

                  TABLE 6
    ______________________________________
    ID name EST    EET    LST  LET   RS    START END
    ______________________________________
    11-1-1  3/28   3/28   3/28 3/28  NONE  --    --
    11-1-2  3/28   3/28   3/28 3/28  NONE  --    --
    11-1-3  3/28   3/28   3/28 3/28  NONE  --    --
    11-1-4  3/28   3/28   3/28 3/28  NONE  --    --
    11-2-1  3/28   3/28   3/28 3/28  NONE  --    --
    .
    .
    22-3-4  3/28   3/28   3/28 3/28  NONE  --    --
    23-1-1  3/28   3/28   3/28 3/28  NONE  --    --
    23-1-2  3/28   3/28   3/28 3/28  NONE  --    --
    23-1-3  3/28   3/28   3/28 3/28  NONE  --    --
    23-1-4  3/28   3/28   3/28 3/28  NONE  --    --
    Model 1 3/28   3/28   3/28 3/28  --    --    --
    Model 2 3/28   3/28   3/28 3/28  --    --    --
    ______________________________________

                  TABLE 7
    ______________________________________
    ID name EST    EET    LST  LET   RS    START END
    ______________________________________
    11-1-1  4/1    4/9    4/23 5/1   NONE  --    --
    11-1-2  4/9     4/15  5/17 5/23  NONE  --    --
    11-1-3   4/15  5/6    5/23 6/13  NONE  --    --
    11-1-4  5/6     5/12  6/25 7/1   NONE  --    --
    11-2-1  4/1    4/5    4/27 5/1   NONE  --    --
    .
    .
    22-3-4   7/19   7/23  9/27 10/1  NONE  --    --
    23-1-1   7/22   7/26  9/13 9/17  NONE  --    --
    23-1-2   7/26   7/30  9/17 9/21  NONE  --    --
    23-1-3   7/30  8/5    9/21 9/27  NONE  --    --
    23-1-4  8/5    8/9    9/27 10/1  NONE  --    --
    Model 1 4/1    6/9    4/23 7/1   --    --    --
    Model 2 6/1    8/9    7/24 10/1  --    --    --
    ______________________________________

                  TABLE 8
    ______________________________________
    ID name EST    EET    LST  LET   RS    START END
    ______________________________________
    11-1-1  4/1    4/13   4/23 5/1   NONE  --    --
    11-1-2  4/13   4/19   5/17 5/23  NONE  --    --
    11-1-3  4/19   5/10   5/23 6/13  NONE  --    --
    11-1-4  5/10   5/16   6/25 7/1   NONE  --    --
    11-2-1  4/1    4/5    4/27 5/1   NONE  --    --
    .
    .
    22-3-4  7/19   7/23   9/27 10/1  NONE  --    --
    23-1-1  7/22   7/26   9/13 9/17  NONE  --    --
    23-1-2  7/26   7/30   9/17 9/21  NONE  --    --
    23-1-3  7/30   8/5    9/21 9/27  NONE  --    --
    23-1-4  8/5    8/9    9/27 10/1  NONE  --    --
    Model 1 4/1    6/13   4/1  7/1   --    --    --
    Model 2 6/1    8/9    7/24 10/1  --    --    --
    ______________________________________

                  TABLE 9
    ______________________________________
    ID name EST    EET    LST  LET   RS    START END
    ______________________________________
    11-1-1  4/1    4/13   4/23 5/1   A     4/1   4/13
    11-1-2  4/13   4/19   5/17 5/23  NONE  --    --
    11-1-3  4/19   5/10   5/23 6/13  NONE  --    --
    11-1-4  5/10   5/16   6/25 7/1   NONE  --    --
    11-2-1  4/1    4/5    4/27 5/1   NONE  --    --
    .
    .
    22-3-4  7/19   7/23   9/27 10/1  NONE  --    --
    23-1-1  7/22   7/26   9/13 9/17  NONE  --    --
    23-1-2  7/26   7/30   9/17 9/21  NONE  --    --
    23-1-3  7/30   8/5    9/21 9/27  NONE  --    --
    23-1-4  8/5    8/9    9/27 10/1  NONE  --    --
    Model 1 4/1    6/13   4/23 7/1   --    --    --
    Model 2 6/1    8/9    7/24 10/1  --    --    --
    ______________________________________

                  TABLE 10
    ______________________________________
    ID name EST    EET     LST  LET   RS  START END
    ______________________________________
    11-1-1  4/1    4/13    4/23 5/1   A   4/1   4/13
    11-1-2   4/13  4/21    5/17 5/23  D    4/13 4/21
    11-1-3  5/3    6/1     5/23 6/13  A   5/3   6/1
    11-1-4  6/7    6/15    6/25 7/1   A   6/7   6/15
    11-2-1  4/1    4/7     4/27 5/1   C   4/1   4/7
    .
    .
    22-3-4  10/4   10/8    9/27 10/1  B   10/4  10/8
    23-1-1   9/20  9/24    9/13 9/17  C    9/20 9/24
    23-1-2   9/26  9/30    9/17 9/21  C    9/26 9/30
    23-1-3   9/30  10/8    9/21 9/27  C    9/30 10/8
    23-1-4  10/10  10/14   9/27 10/1  C   10/10 10/14
    Model 1 4/1    7/8     4/23 7/1   --  --    --
    Model 2 6/1    10/14   7/24 10/1  --  --    --
    ______________________________________

                  TABLE 11
    ______________________________________
    Desired end Scheduled
                         Number of processes allocated
    date        date     to chief designers
    ______________________________________
    6/1          7/13     6
    7/1         7/8      19
     7/15        7/13    22
    8/1         8/5      25
    9/1         8/5      25
    10/1        9/9      26
    ______________________________________

                  TABLE 12
    ______________________________________
    Section            Designer Major item
    ______________________________________
    First development section
                       A, B, C  11, 13
    Second development section
                       D, E     12
    ______________________________________

                  TABLE 13
    ______________________________________
    Machine Obverse-side
                      Obverse-side
                                Reverse-side
                                        Reverse-side
    name    grinding  painting  grinding
                                        painting
    ______________________________________
    A       1         x         1       x
    B       1         x         1       x
    C       x         1         x       1
    D       x         1         x       1
    ______________________________________

                  TABLE 14
    ______________________________________
    Product type
              Lot number Earliest start time
                                      Required time
    ______________________________________
    Product type 1
              1          0            10
    Product type 1
              2          4            14
    Product type 1
              3          8            18
    Product type 1
              4          12           22
    Product type 1
              5          16           26
    Product type 2
              1          0            10
    Product type 2
              2          2            12
    Product type 2
              3          4            14
    Product type 2
              4          6            16
    Product type 2
              5          8            18
    Product type 2
              6          10           20
    Product type 2
              7          12           22
    Product type 2
              8          14           24
    Product type 3
              1          0            10
    Product type 3
              2          2            12
    Product type 3
              3          4            14
    Product type 3
              4          6            16
    Product type 3
              5          8            18
    Product type 3
              6          10           20
    Product type 3
              7          12           22
    Product type 3
              8          14           24
    ______________________________________

                  TABLE 15
    ______________________________________
    ID name EST    EET    LST  LET   RS    START END
    ______________________________________
    1-1-1    0      1      6    7    NONE  --    --
    1-1-2    1      2      7    8    NONE  --    --
    1-1-3    2      3      8    9    NONE  --    --
    1-1-4    3      4      9   10    NONE  --    --
    1-2-1    4      5     10   11    NONE  --    --
    .
    .
    3-7-4   15     16     21   22    NONE  --    --
    3-8-1   14     15     20   21    NONE  --    --
    3-8-2   16     17     21   22    NONE  --    --
    3-8-3   17     18     22   23    NONE  --    --
    3-8-4   18     19     23   24    NONE  --    --
    ______________________________________

                  TABLE 16
    ______________________________________
    ID name EST    EET    LST  LET   RS    START END
    ______________________________________
    1-1-1    0      1      6    7    B     0     1
    1-1-2    1      2      7    8    NONE  --    --
    1-1-3    2      3      8    9    NONE  --    --
    1-1-4    3      4      9   10    NONE  --    --
    1-2-1    4      5     10   11    NONE  --    --
    .
    .
    3-7-4   15     16     21   22    NONE  --    --
    3-8-1   14     15     20   21    NONE  --    --
    3-8-2   16     17     21   22    NONE  --    --
    3-8-3   17     18     22   23    NONE  --    --
    3-8-4   18     19     23   24    NONE  --    --
    ______________________________________

                  TABLE 17
    ______________________________________
    ID name EST    EET    LST  LET   RS    START END
    ______________________________________
    1-1-1    0      1      6    7    B      0     1
    1-1-2    1      2      7    8    D      1     2
    1-1-3    2      3      8    9    B      2     3
    1-1-4    3      4      9   10    D      3     4
    1-2-1    4      5     10   11    B      4     5
    .
    .
    3-7-4   15     16     21   22    C     21    22
    3-8-1   14     15     20   21    B     18    19
    3-8-2   16     17     21   22    C     19    20
    3-8-3   17     18     22   23    B     21    22
    3-8-4   18     19     23   24    C     22    23
    ______________________________________

                  TABLE 18
    ______________________________________
    Product type
              Lot number Earliest start time
                                      Required time
    ______________________________________
    Product type 1
              1          0            10
    Product type 1
              2          4            14
    Product type 1
              3          8            18
    Product type 1
              4          12           22
    Product type 1
              5          16           26
    Product type 2
              1          0            10
    Product type 2
              2          4            14
    Product type 2
              3          8            18
    Product type 2
              4          12           22
    Product type 2
              5          16           26
    Product type 3
              1          0            10
    Product type 3
              2          4            14
    Product type 3
              3          8            18
    Product type 3
              4          12           22
    Product type 3
              5          16           26
    ______________________________________

• Inventors
  Narimatsu, Katsumi; Kojima, Shoichi;
• Assignee
  Kabushiki Kaisha Toshiba (Kawasaki, JP)
• Published
  Oct-20-1998
• Current US Classes:
  700/100
  700/108
  700/182
  700/99
  705/7
  705/8
• Application #
  569773
• International Classes
  G06F 017/60; G06F 017/50
• Field of Search
  364/468.03 364/468.05 364/468.06 364/468.15 364/474.24 395/207 395/208 705/7 705/8
• Examiner
  Hayes; Gail O.
• Agent
  Finnegan, Henderson, Farabow, Garrett & Dunner, L.L.P.
• US Patent References:
  4852001
  5408663