Scheduling optimizer

• US 5,890,134 A
• Filed: 02/16/1996
• Issued: 03/30/1999
• Est. Priority Date: 02/16/1996
• Status: Expired due to Term

• Current Assignee: Mcdonnell Douglas Corporation (The Boeing Co.)
• Original Assignee: Mcdonnell Douglas Corporation (The Boeing Co.)
• Inventors: Fox, Barry Ross
• Primary Examiner(s): Poinvil, Frantzy
• Application Number:
  US08/602,966
• Time in Patent Office: 1,138 Days
• Field of Search: 705/8, 705/9, 364/468.05-468.1, 395/670-674, 395/557
• US Class Current: 705/7.24
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/06313 Resource planning in a project environment
• CPC Class Codes: G06Q 10/06314 Calendaring for a resource

Abstract

A schedule optimizing algorithm improves scheduling quality, reducing a schedules cycle time and requiring only marginal increase in computer execution time. Lower quality computerized scheduling programs are substantially improved through the additional steps of sequential left time shifting and right time shifting of respective chronologically sorted completion time and starting time task listings.

Claims

1. A computer assisted method of optimizing a preliminary schedule for performing a plurality of scheduled tasks that collectively complete a project, said preliminary schedule specifying no less than a start time, a completion time, identification, and resource requirements for each of the plurality of tasks in which any constraints associated with each resource are respected and the plurality of tasks complies with constraints on the order of performance of any one task relative to other tasks defined in the schedule, which includes the step of:

(a) inspecting completion times for said plurality of scheduled tasks in said preliminary schedule and determining latest completion time of any of said scheduled tasks;

(b) defining a completion time boundary, said boundary comprising a time equal to or later than said latest completion time;

(c) inspecting said start times for each of said plurality of scheduled tasks in said preliminary schedule and determining the earliest time of any of said plurality of scheduled tasks;

(d) defining a commencement time boundary, said boundary comprising a time at least equal to and no later than an earliest commencement time;

(e) sorting said plurality of scheduled tasks in said preliminary schedule into chronological order by completion times to derive a temporary chronological listing comprising the completion times for each task;

(f) following said sorting and commencing with one of said tasks in said temporary chronological listing having said latest completion time and continuing with the remaining ones of said tasks in reverse chronological order by completion time

(f1) rescheduling each task in said temporary chronological listing to a new completion time that is as close to said completion time boundary as is permissible without violation of any constraint associated with such task and, based on the duration of respective tasks, to a new start time, said rescheduling being without violation of any constraint associated with such task, whereby each task is assigned a new completion and start time to create a first revised temporary listing of tasks arranged in the order found in said derived temporary listing; and

,

(g) sorting said plurality of tasks in said first revised temporary listing into chronological order by commencement times to derive a second temporary chronological listing comprising the start times for each task;

(h) commencing with one of said tasks in said second temporary chronological listing having the earliest start time and continuing with the remaining ones of said tasks in ascending chronological order by start time,

(h1) rescheduling each task in said second temporary chronological listing to a new start time that is as close to said commencement time boundary as is permissible without violation of any constraint associated with such task and, based on the duration of said respective tasks to a new completion time, said rescheduling being without violation of any constraint associated with such task, whereby each task is again assigned a new start time and completion time to create a third listing of tasks arranged in the same order found in said second temporary chronological listing, said third listing of tasks comprising an optimized schedule.

2. The method as defined in claim 1, wherein the step (f1) of rescheduling includes the step of:

(f1)(a)unscheduling all tasks in said temporary chronological listing by removing the associated start and completion times thereof prior to assigning a completion time for any of said tasks.

3. The method as defined in claim 1, wherein the step (f1) of rescheduling includes the steps of:

(f1) (a) removing the associated start time of the task having the latest completion time;

(f1) (b) rescheduling said respective tasks to a new completion time that is as close in time period to said completion time boundary as is permissible without violating any constraint associated with said tasks; and

,

(f1) (c) based on the respective duration of said respective tasks, assigning a new start time for said respective tasks without violating any constraint associated with said tasks; and

(f1) (d) repeating steps (f1) (a) through (f1) (c) in reverse chronological order by completion time for each of said tasks.

4. The method of claim 1, further including the computer assisted method of generating said schedule for optimizing which comprises the steps of:

(1) listing no less than the identification of and the duration time anticipated for completion of each of said plurality of tasks necessary to complete said project and, with respect to each of said tasks, any constraints associated therewith, including, for each respective task, the identification of any other task that requires completion prior to commencement of the respective task and any resources required by said respective task; and

(2) formulating a preliminary schedule for performance of said plurality of tasks, in which each of said tasks is completed without violation of a respective associated constraint, said preliminary schedule, including, for each of said tasks, at least a start time and a completion time.

5. The method as defined in claim 1, further comprising the steps of accepting the optimized schedule derived from steps (a) through (h) and repeating thereon steps (a) through (h) to derive a further optimized schedule.

6. The method as defined in claims 1, 2, 3, 4 or 5, further comprising the step of displaying said optimized schedule.

7. A programming element for an electronic digital computer comprising a programming medium and program data means resident on said medium for actuating a computer to execute a method as set forth in claims 1 or 4.

8. A computer assisted method of generating a schedule for performing a plurality of scheduled tasks that collectively complete a project, said method being carried out with the aid of a programmed computer, said method comprising the steps of:

(1) listing no less than the identification of and the duration time anticipated for completion of each of a plurality of tasks necessary to complete said project and, with respect to each of said tasks, any constraints associated therewith, including, for each respective task, the identification of any other task that requires completion prior to commencement of the respective task and any resources required by said respective task; and

(2) formulating a preliminary schedule for performance of said plurality of tasks, in which each of said tasks is completed without violation of a respective associated constraint, said preliminary schedule, including, for each of said tasks, at least a start time and a completion time;

(a) inspecting each of said completion times for said plurality of scheduled tasks in said preliminary schedule and determining the latest completion time of any of said tasks scheduled therein;

(b) defining a completion time boundary, said boundary comprising a time equal to or later than said latest completion time;

(c) inspecting each of said start times for each of said plurality of scheduled tasks in said preliminary schedule and determining the earliest start time of any of said plurality of scheduled tasks therein;

(d) defining a commencement time boundary having an earliest commencement time, said boundary comprising a time at least equal to and no later than said earliest commencement time;

(e) sorting said plurality of scheduled tasks in said preliminary schedule into chronological order of the respective completion times of each of said tasks to derive a temporary listing of completion times for each task in descending chronological order, wherein the first task initially scheduled for completion in said plurality of scheduled tasks appears first in said listing and the last task initially scheduled for completion in said plurality of scheduled tasks appears last in said listing;

(f) commencing with said last task in said temporary listing and continuing through said temporary listing in reverse chronological order of completion times,

(f)(1) unscheduling the respective preliminarily scheduled tasks by removing the associated start and completion times; and

(f)(2) rescheduling the respective tasks to a new completion time that is as close in time period to said completion time boundary as is permissible without violating any constraint associated with said tasks; and

,

(f)(3) based on the respective duration of said respective tasks, assigning a new start time for said respective tasks, to define a second temporary listing in which said tasks are ordered in the same order as in said first named temporary listing;

(g) sorting said plurality of tasks in said second temporary listing into chronological order of the respective start times of each of said tasks to derive a further temporary listing of start times for each task in descending chronological order of start times, wherein the first task initially scheduled for commencement in said plurality of tasks in said second temporary listing appears first in said further temporary listing and the last task initially scheduled for commencement in said plurality of tasks in a right shift task temporary listing appears last in said further temporary listing;

(h) commencing with the first task in said further temporary listing and continuing through said further temporary listing in chronological order of commencement times,

(h1) unscheduling the respective scheduled task and,

(h2) rescheduling the respective tasks to a new commencement time that is as close in time to a left boundary as is permissible without violating any constraint associated with such respective task; and

(h3) based on the respective duration of said respective task, assigning a new completion time for said respective tasks, to define an optimized schedule of tasks for completion of a given task.

9. The method as defined in claim 8, further comprising the step of displaying said optimized schedule.

10. A programming element for an electronic digital computer comprising a programming medium and program data means resident on said medium for actuating a computer to execute a method as set forth in claim 8.

11. A computer assisted method of generating a schedule for performing a plurality of scheduled tasks that collectively complete a project, said method being carried out with the aid of a programmed computer, said method comprising the steps of:

(1) listing no less than the identification of and the duration time anticipated for completion of each of a plurality of tasks necessary to complete said project and, with respect to each of said tasks, any constraints associated therewith, including, for each respective task, the identification of any other task that requires completion prior to commencement of the respective task and any resources required by said respective task; and

(2) formulating a preliminary schedule for performance of said plurality of tasks, in which each of said tasks is completed without violation of a respective associated constraint, said preliminary schedule, including, for each of said tasks, at least a start time and a completion time;

(a) inspecting said completion times for said plurality of scheduled tasks in said preliminary schedule and determining the latest completion time of any of said scheduled tasks;

(b) defining a completion time boundary, said boundary comprising a time equal to or later than said latest completion time;

(c) inspecting said start times for each of said plurality of scheduled tasks in said preliminary schedule and determining the earliest time of any of said plurality of scheduled tasks;

(d) defining a commencement time boundary, said boundary comprising a time at least equal to and no later than said earliest commencement time;

(e) sorting said plurality of scheduled tasks in said preliminary schedule into chronological order by completion times to derive a first temporary chronological listing comprising the completion times for each task;

(f) following said sorting and commencing with one of said tasks in said temporary chronological listing having said latest completion time and continuing with the remaining ones of said tasks in reverse chronological order by completion time

(f1) rescheduling each task in said temporary chronological listing to a new completion time that is as close to said completion boundary time as is permissible without violation of any constraint associated with such task and, based on the duration of said respective tasks, to a new start time, said rescheduling being without violation of any constraint associated with said tasks, whereby each task is assigned a new completion and start time to create a first revised temporary listing of tasks arranged in the order found in said first derived temporary listing; and

,

(g) sorting said plurality of tasks in said first revised temporary listing into chronological order by commencement times to derive a second temporary chronological listing comprising the start times for each task;

(h) commencing with one of said tasks in said second temporary chronological listing having the earliest start time and continuing with the remaining ones of said tasks in ascending chronological order by start time,

(h1) rescheduling each task in said second temporary chronological listing to a new start time that is as close to said commencement boundary time as is permissible without violation of any constraint associated with said tasks and, based on the duration of said respective tasks, to a new completion time, said rescheduling being without violation of any constraint associated with said tasks, whereby each task is again assigned a new start time and completion time to create a third listing of tasks arranged in the same order found in said second temporary chronological listing, said third listing of tasks comprising an optimized schedule.

12. A computer assisted method of optimizing a preliminary schedule for performing a plurality of scheduled tasks that collectively complete a project, said preliminary schedule specifying a start time and a completion time that define a respective duration, said preliminary schedule respecting any constraints associated with each task including constraints on the order of performance of any one task relative to other tasks, the method including the steps of:

defining a completion time boundary no earlier than the latest completion time of any of said scheduled tasks;

defining a commencement time boundary no earlier than the earliest start time of any of said plurality of scheduled tasks;

rescheduling each task such that the completion time for each task is rescheduled to a first new completion time that is as close to said completion time boundary as is permissible without violation of any constraint associated with such task, wherein said rescheduling step further alters the start time for each task based on the duration of each respective task to define a first new start time such that each task is assigned a first new completion time and a first new start time as a result of said rescheduling step to thereby create a revised temporary listing of tasks;

further rescheduling each task such that the first new start time for each task is rescheduled to a second new start time that is as close to said commencement time boundary as is permissible without violation of any constraint associated with such task, wherein said rescheduling step further alters the first new completion time for each task based on the duration of each respective task to define a second new completion time such that each task is assigned a second new completion time and a second new start time as a result of said further rescheduling step to thereby create a listing of tasks comprising an optimized schedule.

13. The method as defined in claim 12 further comprising the step of unscheduling all tasks in said preliminary schedule by removing the associated start time and completion time for each task prior to the initial step of rescheduling each task.

14. The method as defined in claim 13, wherein said initial step of rescheduling each task includes the steps of:

removing the associated start time of each task;

rescheduling the completion time for each tasks to a first new completion time that is as close in time period to said completion time boundary as is permissible without violating any constraint associated with said tasks; and

rescheduling the start time associated with each task based on the duration of each task to a first new start time without violating any constraint associated with said task.