Source: http://www.docstoc.com/docs/39861395/Job-Scheduling-Method-And-System---Patent-4852001
Timestamp: 2013-05-23 02:10:37
Document Index: 632354886

Matched Legal Cases: ['art 101', 'art 102', 'art 103', 'art 104', 'art 105', 'art 102', 'art 102', 'art 102', 'art 102', 'art 103', 'art 104', 'art 104']

Job Scheduling Method And System - Patent 4852001 Abstract
Inventors:Isao Tsushima; Norihisa Komoda; Masao Yagi; Tetsuo Kusuzaki
Filed Date: 7/17/1987
Issue Date: 7/25/1989
US Patent Application: 07/074,767
Patent number: 4852001
Other US Classes:Data Processing:Generic Control Systems Or Specific Applications (700/100)Data Processing:Generic Control Systems Or Specific Applications (700/99)
International Classes:G06Q 10/0(20060101); G05B 19/418(20060101); G06F 15/46(0)
Tags:Job scheduling method and system, Tsushima, et al., Isao Tsushima, Norihisa Komoda, Masao Yagi, Tetsuo Kusuzaki, Application number 07 074-767, Data Processing:Financial Business Pr..., Data Processing:Generic Control Syste..., patent search, scheduling system, Forward References, Company Search, Patent Number, start times, Document Number, Family Claims, Patent and Trademark Office, Patent Attorney
3643227N/ASmith et al.2/1/1972
3648253N/AMullery et al.3/1/1972
3662401N/ACollins et al.5/1/1972
3703725N/AGomersall11/1/1972
4183083 Method of operating a multiprogrammed computing systemChatfield1/1/1980
4383298 Plant maintenance control systemHuff et al.5/1/1983
4580207 Numerical control data dividing and editing apparatus for numerical control machine toolArai et al.4/1/1986
5031089 Dynamic resource allocation scheme for distributed heterogeneous computer systemsLiu, et al.7/9/1991
5040123 Expert system schedulerBarber, et al.8/13/1991
5050088 Production control system and methodBuckler, et al.9/17/1991
5093794 Job scheduling systemHowie, et al.3/3/1992
5099431 Automated re-work shop order scheduling systemNatarajan3/24/1992
5170355 Apparatus and a method for controlling the release of jobs from a pool of pending jobs into a factoryHadavi, et al.12/8/1992
5216619 Path management for a process systemDunbar, Jr., et al.6/1/1993
5343387 Cyclic maintenance work schedule table preparation systemHonma, et al.8/30/1994
5375061 Manufacturing management and apparatus for a semiconductor deviceHara, et al.12/20/1994
5375239 Use of build status indicators in connection with building of complex computer programs from source code partsMortson12/20/1994
5396603 Data processor having resources and execution start control for starting execution of succeeding instruction in resource before completion of preceding instructionTamaki, et al.3/7/1995
6038539 Job scheduling system for designating procedure start timesMaruyama, et al.3/14/2000
5440493 Lot transporting system between stations having different manufacturing equipmentDoida8/8/1995
5471614 Database system concurrency control apparatus using timestamps and processing time estimationKakimoto11/28/1995
5495430 Process time estimating apparatusMatsunari, et al.2/27/1996
5016170 Task managementPollalis, et al.5/14/1991
5053970 Work scheduling methodKurihara, et al.10/1/1991
5111391 System and method for making staff schedules as a function of available resources as well as employee skill level, availability and priorityFields, et al.5/5/1992
5155679 Set-up optimization for flexible manufacturing systemsJain, et al.10/13/1992
5155851 Routing an incoming data stream to parallel processing stationsKrishnan10/13/1992
5233533 Scheduling method and apparatusEdstrom, et al.8/3/1993
5261099 Synchronous communications scheduler allowing transient computing overloads using a request bufferBigo, et al.11/9/1993
5303144 Computer aided planning support systemKawashima, et al.4/12/1994
5305221 Real world modeling and control process for integrated manufacturing equipmentAtherton4/19/1994
5329456 Material flow control deviceKaihara, et al.7/12/1994
5361362 Adaptive job scheduling for multiprocessing systems with master and slave processors executing tasks with opposite anticipated execution times respectivelyBenkeser, et al.11/1/1994
5440681 Method and apparatus for display and interactive modification of the tasks in a production planKudo8/8/1995
5513354Fault tolerant load management system and methodDwork, et al.4/30/1996
6115642Systems and methods for facilitating the exchange of information between separate business entitiesBrown, et al.9/5/2000
6115641Systems and methods for facilitating the exchange of information between separate business entitiesBrown, et al.9/5/2000
6131093Job scheduling systemMaruyama, et al.10/10/2000
5559710Apparatus for control and evaluation of pending jobs in a factoryShahraray, et al.9/24/1996
5568635Physical memory allocation system, program execution scheduling system, and information processorYamaguchi10/22/1996
5604908 Computer program product for using build status indicators in connection with building of complex computer programs from source code partsMortson2/18/1997
5721686 Method and apparatus for control and evaluation of pending jobs in a factoryShahraray, et al.2/24/1998
5727210 Fault tolerant load management system and methodDwork, et al.3/10/1998
5619695 Method and apparatus for scheduling resourcesArbabi, et al.4/8/1997
5748478 Output management of processing in a manufacturing plantPan, et al.5/5/1998
5752030 Program execution control in parallel processor system for parallel execution of plural jobs by selected number of processorsKonno, et al.5/12/1998
5787439 Method and system for maintaining a preferred sequence for accessing a plurality of objectsTaysom7/28/1998
5671338 Constraint evaluation system, expert system, and constraint evaluation methodAraki, et al.9/23/1997
6269410 Method and apparatus for using system traces to characterize workloads in a data storage systemSpasojevic7/31/2001
5826236 Method for allocating resources and processes for design and production plan schedulingNarimatsu, et al.10/20/1998
5826238 Daily target generation and machine allocation with priorityChen, et al.10/20/1998
5838565 Manufacturing control method for IC plant batch sequential machineHsieh, et al.11/17/1998
6301574 System for providing business informationThomas, et al.10/9/2001
5848395 Appointment booking and scheduling systemEdgar, et al.12/8/1998
5918219 System and method for estimating construction project costs and schedules based on historical dataIsherwood6/29/1999
5923552 Systems and methods for facilitating the exchange of information between separate business entitiesBrown, et al.7/13/1999
6336101 Tracking of computer components allocated during configuration of computer systems and networks by a simplified user friendly configuration processDean, et al.1/1/2002
5889673 Manufacturing method and system for dynamic dispatching of integrated circuit wafer lotsPan, et al.3/30/1999
6370508 Interface engine for managing business processes within a multimedia communication-centerBeck, et al.4/9/2002
5963911 Resource allocationWalker, et al.10/5/1999
5991732 Strategical-tactical logistic systemMoslares11/23/1999
6430549 System and method for selectivety defining access to application featuresGershfield, et al.8/6/2002
5978831 Synchronous multiprocessor using tasks directly proportional in size to the individual processors ratesAhamed, et al.11/2/1999
6823315 Dynamic workforce schedulerBucci, et al.11/23/2004
6594537 Automated tissue assay using standardized chemicals and packagesBernstein, et al.7/15/2003
6618742 Method for job impact learningKrum9/9/2003
6618820 Method for configuring an application server systemKrum9/9/2003
6889106 Master production scheduling management system and methodWei5/3/2005
6954737 Method and apparatus for work management for facility maintenanceKalantar, et al.10/11/2005
7082605Contingency planning in a scheduling processAlletson, et al.7/25/2006
7305275Material supply system in semiconductor device manufacturing plantMiyazaki, et al.12/4/2007
7210119Handling unscheduled tasks in a scheduling processPothos, et al.4/24/2007
7222082Business volume and workforce requirements forecasterAdhikari, et al.5/22/2007
7346906Workload management in a computing environmentKelly, et al.3/18/2008
7349863Dynamic planning method and systemPena-Mora, et al.3/25/2008
7415393Reliability buffering technique applied to a project planning modelPena-Mora, et al.8/19/2008
7734478Method and apparatus for inter-pharmacy workload balancing using resource function assignmentsGoodall, et al.6/8/2010
7761333Income tax preparation system for traveling taxpayersKapp7/20/2010
7765108Method and apparatus for inter-pharmacy workload balancingGoodall, et al.7/27/2010
7774134Pharmacy network management system and method for searching for a pharmacy store location with a drive throughBleser, et al.8/10/2010
7827216Method for coordinating relationships between multiple physical entitiesTaysom11/2/2010
7831459System and method for balancing production capacityChao, et al.11/9/2010
7831448Method and apparatus for inter-pharmacy workload balancing using resource function assignmentsGoodall, et al.11/9/2010
7860730Method and apparatus for inter-pharmacy workload balancingGoodall, et al.12/28/2010
7941325System and method of using a non-retail central filling facility to process pharmacy product prescriptions in a pharmacy retail networkHeald, et al.5/10/2011
8055513Pharmacy network management system and method for searching for a pharmacy store locationBleser, et al.11/8/2011
8079066Multi-domain login and messagingCordell, et al.12/13/2011
8145501System and method for performing pharmacy product filling using non-registered pharmacistsHeald, et al.3/27/2012
g2Wsby467
E78yIcc30
ewghwehws28
huangyuarong45
System And Method For Best Effort Scheduling - Patent 8144669
O5XwpfV14
rudy.opp33
Claims We claim:1. A job scheduling method for scheduling of job allocation to various resources comprising the steps of:inputting data associated with jobs and resources;allocating a workload of each job to each time unit along a time axis in units of job;allocating said workload to said each time unit in units of resource type;calculating an initial workload for all resources at said each time unit, in accordance with said workload allocated in units of resource type;performing a first workload balancing for a time unit whose initial workload for all resources exceeds a resource capacity, so as to make the workload at said time unit within said resource capacity;after said first workload balancing, performing a second workload balancing so as to make the workload allocated in units of resource type within its resource capacity; andoutputting, as a job schedule, each workload at said each time unit obtained by said second workload balancing.2. A job scheduling method according to claim 1, wherein said first workload balancing step includes a step of performing at least one of right-shift, left-shift and cutting processings for an excessive workload at said each time unit.3. A job scheduling method according to claim 1, wherein said second workload balancing step includes a step of performing a relieving function for relieving a processing by one resource to another resource.4. A job scheduling system for scheduling of job allocation to various resources comprising:means for inputting data associated with jobs and resources;means for allocating a workload of each job to each time unit along a time axis in units of job;means for allocating said workload to said each time unit in units of resource type;means for calculating an initial workload for all resources at said each time unit, in accordance with said workload allocated in units of resource type;means for performing a first workload balancing for a time unit whose initial workload for all resources exceeds a resource capacity, so as to make the workload at said time unit within said resource capacity;means for, after said first workload balancing, performing a second workload balancing so as to make the workload allocated in units of resource type within its resource capacity; andmeans for outputting, as a job schedule, each workload at said each time unit obtained by said second workload balancing.5. The job scheduling system according to claim 4, wherein said means for performing the first workload balancing includes at least one of right-shift, left-shift and cutting processing means for an excessive workload at said each time unit.6. The job scheduling system according to claim 4, wherein said means for performing the second workload balancing includes relieving means for relieving a processing by one resource to another resource. Description BACKGROUND OF THE INVENTIONThe present invention relates to a scheduling method for allocating a time and a job to each resource (person, installation), and more particularly to a job scheduling method suitable for a project which needs to consider a number of restrictionsof the job allocation.In order to complete a given project with limited resources (persons and installations), it is important to develop a schedule capable of allocating a suitable time and a suitable job to each resource. Without a proper schedule, jobs mayconcentrate on a particular resource or no job may be allocated to another particular resource thus leading to an inability to complete a workload per day.Job scheduling has applications to various fields. One practical scheduling method is known described, for example, in "ACTIVITY NETWORK", by Elmagraphy, pp. 144 to 149, JOHN WILEY & SONS, March 1977. A brief description of a conventionalsystem of this type will be given with reference to FIG. 2.First, an earliest start time is allocated to each job (indicated by A to E in the Figure) to obtain an initial workload allocation result. In the example shown in FIG. 2, it is assumed that two persons are necessary for each job and the totalnumber of persons is four. According to the initial workload allocation result, six persons are required at a peak workload, which means a shortage of two persons. With a conventional system, workload balancing has been carried out to balance theworkload within a limited number of persons. Since a start time for each job is given an earliest start time at the initial workload allocation, there is a job or jobs which can be shifted to the right along the time axis, i.e., can be delayed. Therefore, a job (illustratively job F) which can be completed at the latest finish time is selected among the jobs and shifted to the right to the latest start time before the appointed time (time 20 in this example). Succeedingly, the similarprocedure as above is repeated until the workload is balanced within the resource capacity.The above conventional system, however, cannot be applied to various fields and is not suitable for the application to other than the manufacturing industry.SUMMARY OF THE INVENTIONIt is an object of the present invention to provide a job scheduling method having a wide range of applications, an excellent optimum status, a good processing efficiency and a high descriptive nature.To achieve the above object, scheduling in various fields has been analyzed to definitely show problems arising if the above conventional system is applied to the fields other than the manufacturing industry. The problems have been solved in themanner as described in the following, taking a job scheduling in a super market as an example.(1) An alternative resource can be used for each job. According to the present invention, although a register clerk for example should generally be a clerk, a part timer or temporary employee does the work if the register clerk is busy atanother work. If not possible, a management person is impelled to do the work. According to the conventional system, each resource doing a job is defined only in a general sense.(2) A latest start time can be given to a particular job. According to the present invention, a finish time of an order for example can be given a time as late the order due time as possible. According to the conventional system, all jobs aregiven earliest start times at the initial workload allocation. A finish time may be given an order due time, but it is a mere chance.(3) As means for balancing a peak workload in excess of the resource capacity, not only start time delaying function but also start time hastening function, job cutting function and job relieving function are added. It is necessary for the orderjob described in the above (2) to be shifted to the left if a start time is given a latest start time at the workload allocation. Further, if there is a peak workload in excess of the resource capacity even after the shift of a start time, a job cuttingof "a certain work is not done today" is effected in an actual job scheduling. Furthermore, even if the total workload does not exceed the capacity for all resources, a peak workload of a certain resource type may exceed its capacity if a resource typemost suitable for each job at a time is allocated as described in the above (1). In this case, a job relieving function for relieving the job by another resource is effected to balance the peak workload.(4) A priority order of jobs is considered in balancing the workload. There occurs a case where a job is not desired to be shifted even if it has a room for shift. There is also a job which is not desired to be cut or relieved as described inthe above (3). For example, a shop clean-up work should be cut rather than a register work which is more directly related to customer services.In view of the above, a job scheduling system according to this invention is provided with means for describing initial workload allocation, and knowledge and know-how for the workload allocation, in the form of rules.According to the present invention, by means of the above-described rule description means, it is possible to realize a system having a wide application field, in which system it is easy to describe, add and modify various knowledge and know-howfor the workload allocation and the like. Further, an improved optimum status and processing efficiency can be attained because of the inclusion of the fundamental workload balancing functions described in the above (3). BRIEF DESCRIPTION OF THEDRAWINGSFIG. 1 is a functional block diagram showing an embodiment of a job scheduling system with various tables according to the present invention;FIG. 2 is a schematic diagram illustrating a conventional system;FIG. 3 is an initial workload allocation rule table;FIG. 4 is a workload allocation rule table (for all resources);FIG. 5 is a workload allocation rule table (for each resource type);FIG. 6 is a capacity data table (for each resource type);FIG. 7 is a capacity data table (for all resources);FIG. 8 is a flow chart showing a processing by the initial workload allocation part;FIG. 9 is a workload allocation result table (for each job);FIG. 10 is a workload allocation result table (for each resource type);FIG. 11 is a workload allocation result table (for all resources);FIG. 12 is a flow chart showing a processing by the workload allocation part;FIG. 13 is a flow chart showing a processing by the workload allocation part for all resources, which is a part of the flow chart of FIG. 12;FIG. 14 is a flow chart showing the detail of the start time delaying and hastening functions by the workload balancing means for all resources;FIG. 15 is a flow chart showing the detail of the job cutting function by the workload balancing means for all resource; andFIG. 16 is a flow chart showing the detail of the job relieving function which is the workload balancing means for each resource type. DESCRIPTION OF THE PREFERRED EMBODIMENTSFIG. 1 is a functional block diagram showing an embodiment of a job scheduling system with various tables according to the present invention. The relationship between each block and table will be detailed later, as it becomes necessary, withreference to other figures.A main control part 101 sequentially actuates and controls a data input part 102, an initial workload allocation part 103, a workload balancing part 104 and an output part 105, to thereby obtain a resultant output.The input part 102 stores input data regarding rules and resource capacities in each table 106 to 113. The description for the tables will now be given hereinafter.FIG. 3 shows the structure of an initial workload allocation rule table 106. As a descriptive format for initial workload allocation rules, there is provided a basic statement of "as an initial workload for job [P.sub.1 ], resource type [P.sub.2] and number of persons [P.sub.3 ] are allocated between [P.sub.4 ] o'clock to [P.sub.5 ] o'clock". P.sub.1 to P.sub.5 are given names and numerals for each job. The input part 102 stores the contents of a rule in the table 106 shown in FIG. 3, inaccordance with the names and numeral values P.sub.1 to P.sub.5. Namely, the particular job name and resource type inputted as P.sub.1 and P.sub.2 are converted respectively into job number P.sub.1 ' and resource type number P.sub.2 ' by an editor inthe computer for the purpose of simplicity of processing. The correspondence between them is decided when a rule is inputted. The inputted number of persons P.sub.3 is stored directly in the table. The particular inputted times P.sub.4 and P.sub.5 areconverted respectively into a start time unit number P.sub.4 ' and an end time unit number P.sub.5 ' by the editor in the computer. This correspondence between them is also decided when the rule is inputted. With this initial workload allocation rule,it is possible to allocate most suitable time units to the workload of a job.FIG. 4 shows the structure of a workload balancing rule table (for all resources) 107. As a descriptive format for workload balancing rules for all resources, there is provided a basic statement of "IF (workload exceeds the resource capacity),THEN (apply workload balancing means [P.sub.4 ] to job [P.sub.1 ] between [P.sub.2 ] o'clock and [P.sub.3 ] o'clock, with priority [P.sub.5 ])". The input part 102 stores the contents of a rule in the table 107 shown in FIG. 4, in accordance with thenames and numeral values P.sub.1 to P.sub.5. One of the names, i.e., right-shift, left-shift and cut, of workload balancing means is designated. A priority order during application of a rule is designated as [P.sub.5 ].The names and times inputted as P.sub.1 to P.sub.3 are converted by the editor in the computer into corresponding numbers P.sub.1 ' to P.sub.3 '.FIG. 5 shows the structure of a workload balancing rule table (for each resource type) 108. As a descriptive format for workload balancing rules for each resource type, there is provided a basic statement of "IF (workload exceeds the resourcetype capacity), THEN (relieve job [P.sub.2 ] by resource type [P.sub.3 ], with priority [P.sub.4 ])". The input part 102 stores the contents of a rule in the table 108 shown in FIG. 5, in accordance with the names and numerical values P.sub.1 toP.sub.4.The names P.sub.1 to P.sub.3 are converted by the editor in the computer into corresponding numbers P.sub.1 ' to P.sub.3 '.FIG. 6 shows the structure of a capacity data table (for each resource type) 109. The table stores capacity data l (i, j) for each resource type number (i) and each time unit number (j). Based on the data, it is evaluated if the workload foreach resource type is in excess of the resource type capacity.FIG. 7 shows the structure of a capacity data table (for all resources) 110. The table stores capacity data (for all resources) l (j) for each time unit number ##EQU1##Next, the initial workload allocation part 103 will be described. By this part, an initial workload allocation is performed. The processing flow is shown in FIG. 8. First, at step 801 a workload of each job is allocated along the time axis(i.e., in a workload allocation result table (for each job) 111, and in a workload allocation result table (for each resource type) 112) as an initial workload, in accordance with the information in the initial workload allocation rule table 106. Particularly, the following processing is conducted for each job: ##EQU2## wherein m(k, j) denotes an item in the workload allocation result table (for each job) 111 shown in FIG. 9, which item represents a workload of a job number k at a time unitnumber j, and wherein n(i, j) denotes an item in the workload allocation result table (for each resource type) 112 shown in FIG. 10, which item represents a workload for a resource type number i at a time unit number j.Next, at step 802 an initial workload of resources per each time unit j is calculated in accordance with the information in the workload allocation result table (for each resource type) 112 shown in FIG. 10, and the results are stored in aworkload allocation result table (for all resources) shown in FIG. 11. The processing is performed by ##EQU3## for j=1 to J, wherein n(j) denotes an item in the workload allocation result table (for all resources) 113 shown in FIG. 11, which itemrepresents a workload for all resources at a time unit number j.Next, the workload balancing part 104 will be described. In this part, a workload balancing is performed to balance a workload within the resource capacity if the workload is found in excess of the resource capacity at the initial workloadallocation. It is necessary in this case that the workload for all resources be within the resource capacity. To this end, the basic workload allocation functions, i.e., start time delaying and hastening functions 114 and job cutting function 115 arefirst adopted. Thereafter, to make the workload of each resource type within the resource capacity, the job relieving function 116 is adopted. FIG. 12 is a flow chart illustrating such processing.In the flow chart, first at step 1201 it is checked if the resource capacity is larger than the workloads of all resources and resource types. If the capacity is not larger than the workloads, the processing by the workload balancing part 104stops. If the capacity is larger than the workloads, then the flow advances to the next step 1202. If the workload for all resources is not in excess of the capacity, step 1206 follows, whereas if affirmative at step 1202, step 1203 follows. At step1203, it is checked if there is present any available workload balancing means for all resources (right-shift, left-shift or cut) in the workload balancing rule table (for all resources) 107 shown in FIG. 4. This judgement of availability is made inaccordance with control flags in the table. The initial values of the control flags have been set such, that all means are available. If there is no means which indicates that a workload balancing is not possible, the processing stops. If there is anyavailable means, the flow advances to step 1204 whereat means having a highest priority among available workload balancing means (rules) for all resources is selected to conduct a workload balancing.If the workload for all resources becomes within the resource capacity by virtue of the workload balancing at step 1205, the flow advances to the next step 1206. If the capacity is larger than the workloads of all resource types at step 1206,then the processing stops. If not, the flow advances to step 1207 whereat it is checked if there is any available workload balancing means (relieving means) for each resource type in the workload balancing rule table (for each resource type). If not,the processing stops. If affirmative, step 1208 follows to select means having a highest priority order among available workload balancing means to conduct a workload balancing which is performed by the job relieving function 116 shown in FIG. 1. Ifthe workloads become smaller than the capacity for all resource types by the workload balancing at step 1209, the processing stops.Next, the detail of step 1204 of FIG. 12 will be given with reference to FIGS. 13 to 15.As shown in FIG. 13, first at step 1301, means having a highest priority order among available means is derived by referring to the workload balancing rule table (for all resources) 107 shown in FIG. 4. The data P.sub.1 ' to P.sub.5 aresubstituted into q.sub.1 to q.sub.5. Using q.sub.5 storing a name of the workload balancing means, it is checked at step 1302 and 1303 if it represents a right-shift or a left-shift. In case of a right-shift or a left-shift, a workload balancing isperformed to complete such processing. If it is neither a right-shift nor a left-shift, a workload balancing through a cutting function is performed to complete such processing.Next, the detail of step 1304 will be given with reference to FIG. 14.First at step 1401, a time unit number j* is derived whereat a job number q.sub.1 to be right- or left-shifted has a workload in excess of a predetermined number of persons (n(j)-l(j)>0). These data are collectively represented by a set {j*}. Next, at step 1402, j* of {j*} having a maximum n(j*)-l(j*) is derived and represented by j**. The reason for this derivation is that it is proper to balance a peak workload at first. Then at step 1403, it is checked if the workload balancing means isa right-shift. If affirmative, it is checked at step 1404 if J** is smaller than q.sub.3 (latest finish time unit number). If not smaller, it means that a right-shift is not available so that j** is removed from {j**} at step 1405. If smaller, it ischecked at step 1406 if there is a time unit number which can be subjected to a right-shift. In other words, it is checked if there is j which suffices j**<j.ltoreq.q.sub.3 and n(j)-l(j)<0. If not, the flow returns to step 1405. If affirmative,j having a minimum (or minimum workload) n(j)-1 (j) is derived and represented, at step 1407, by j*** which is a or right-shift of j**. To balance the workload one by one minutely, a workload in amount of one person of the job number q.sub.1 at the timeunit number j** is shifted to the time number unit j***. Particularly, the contents of the workload allocation result table (for each job) 111 shown in FIG. 9, the workload allocation result table (for each resource type) 112 shown in FIG. 10 and theworkload allocation result table (for all resources) 113 shown in FIG. 13 are changed as in the following:In the above, i* is obtained, using q.sub.1 as a key, from the initial workload allocation rule table.After completion of step 1408, the flow returns to step 1409 to which step 1405 is also returned. It is checked at step 1409 if there is a time unit number j* whose workload is shiftable. Namely, if the set {j*} is not an empty set (0), theabove processess are repeated. If {j*}=0, selected workload balancing means is caused not applicable. Particularly, the control flag of workload balancing means in the workload balancing rule table (for all resources) 107 shown in FIG. 4 is changedfrom 0 to 1 at step 1410.In case of a left-shift instead of a right-shift as described so far, steps 1411 and 1412 corresponding to steps 1412 and 1406, respectively, are executed. The description therefore is omitted due to a similar operation to the latter steps.The above description has been directed to step 1304 of FIG. 13. Next, the detail of a workload balancing through a cutting operation at step 1305 will be given with reference to FIG. 15.First at step 1501, a time unit number j* is derived whereat a job number q.sub.1 is in condition of n(j)-l(j)>0. These data are collectively represented by a set {j*}. Next, at step 1502, it is checked if the set {j*} is an empty set (0). If {j*} is not equal to 0, j* having a maximum n(j*)-l(j*) is derived and represented by j** at step 1503. A workload of the job number q.sub.1 at time unit number j** is cut by a persons. a is a minimum of {m(q.sub.1, j**), n(j**)-l(j**)}. The firstterm represents a workload which can be cut, whereas the second term represents an amount of excessive workload. Particularly, at step 1504 the contents of the workload allocation result tables are changed as in the following:In the above, i* is obtained, using q.sub.1 as a key, from the initial workload allocation rule table.After completion of the cut operation for the time unit number j**, the j** is removed from the set {j*} at step 1505 to return to step 1502. If the set {j*} is not 0, the similar processes are repeated. If {j*}=0, the flow advances to step1506 whereat selected workload balancing, i.e., cutting means is caused not applicable. Particularly, the control flag of workload balancing means in the workload balancing rule table (for all resources) is changed from 0 to 1.Next, the detail of step 1208 shown in FIG. 12 will be given with reference to FIG. 16. First at step 1601, the time unit number j is set at 1. The control flags of the workload balancing rule table (for each resource type) 108 are allinitialized to be applicable at step 1602. Next at step 1603, a resource type number i* is derived whose workload exceeds its capacity at a time unit number j (i.e., for i sufficing n(i, j)-l(i, j) >0). These data are collectively represented by aset {i*} which designates a resource type having an excessive workload and not subjected to a workload balancing. One of the resource types {i*} is selected and represented by i** at step 1604. The resource type number i** to be balanced is removedfrom the set {i*} at step 1605.The resource type number i** is then subjected to a workload balancing. First at step 1606, a rule with P.sub.1 '-i**, control flag=0 (applicable) and a highest priority order is derived from the workload balancing rule table. The parametersP.sub.2 ' to P.sub.4 are substituted into q.sub.2 to q.sub.4, respectively. If a workload can be entered into a relief destination at step 1607 (i.e., n(q.sub.3, j)-l(q.sub.3, j)<0), and if there is a job number q.sub.2 to be relieved at the timeunit number j at step 1608 (i.e., m(q.sub.2, j).noteq.0), then the relieving processing advances to step 1609. If one of the above two conditions is not met, the rule concerned cannot be used for the relieving operation so that the workload balancingrule is caused not applicable at step 1610. The flow returns to step 1606 to derive a next rule to be applied.At step 1609 performing a workload balancing, a workload in amount of b persons of the resource type number i** at a time unit number j is moved to a resource type number q.sub.3, whereinParticularly, the workload allocation result table (for each workload type) 108 is changed as in the following:If it is decided at step 1611 that the workload after the above relieving operation is not made within its capacity (i.e., if n(i**, j)-l(i**, j)>0), the flow returns to step 1610. If the workload of the resource type number i** is madewithin its capacity, it is checked at step 1612 if there is another resource type number not subjected to a workload balancing (i.e., {i*} =0?). If {i*} is not 0, the flow returns to step 1604. If {i*} is 0, it is checked at step 1613 if the workloadbalancing has been completed for all the time unit numbers (i.e., i=j?). If not (i<J), j+1 is substituted to j at step 1614. If i=J, the processing stops.After the above workload balancing procedure, the output part shown in FIG. 1 outputs the contents of the workload allocation result table (for each job) 111, the workload allocation results table (for each resource type) 112 and the workloadallocation result table (for all resources) 113. However, if the workload is decided not to be within the resource capacity, such a status is informed.According to this embodiment, in contrast with the conventional system, the job can be allocated to any desired time at an initial workload allocation and in addition, left-shift, job cutting and relieving functions can be incorporated. Thus, ajob scheduling having a variety of application fields can be realized. Further, a descriptive format of a rule with a definite statement is provided for expressing the know-how of the workload allocation and balancing, thus making it very easy todescribe, add and modify the know-how. Furthermore, the system includes fundamental scheduling functions so that a suitable job scheduling can be realized in short time by merely changing the know-how.According to the present invention, various conditions on the workload allocation and balancing can be taken into consideration. Thus, a suitable job scheduling can be realized for a variety of application fields to accordingly enable improvedservices and reduced manpower. Further, various conditions can be expressed in the form of rule so that the description, addition and modification of a rule are easy. Furthermore, the system includes fundamental scheduling functions so that even if theconditions to be considered are changed, the system can readily cope with such change.* * * * *
Register and get access to “Job Scheduling Method And System - Patent 4852001”
Login to continue downloading: “Job Scheduling Method And System - Patent 4852001”
7+ Documents Related to “Job Scheduling Method And System - Patent 4852001”