Method of determining a schedule, scheduler and system

• US 20020156669A1
• Filed: 02/26/2002
• Published: 10/24/2002
• Est. Priority Date: 06/27/2000
• Status: Abandoned Application

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Van Der Sterren, William Edward Peter, Verhaegh, Wilhelmus Franciscus Johannes
• Application Number:
  US10/069,742
• Publication Number:
  US 20020156669A1
• Time in Patent Office: Days
• US Class Current: 705/8
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations

Abstract

A scheduler (100) which implements a method for determining a flexible schedule (205) for executing a plurality of tasks (301-308) in a system having a plurality of resources (101-103, 109-113). The schedule (205) comprises for each task (301-308) a starting time, an ending time, an assignment of resources (101-103, 109-113) to said task (301-308), as well as a collection of times and processing speeds. Using this information, the execution of a task can vary in speed when for example multiple tasks need the same resource. To do this, the scheduler first defines a partial schedule using windows (w₀ , . . . , w₁₅) and then determines the length of the windows (w₀ , . . . , w₁₅) and the processing speed of each task in each window using linear programming and column generation.

Claims

1. A method of determining a schedule (205) for executing a plurality of tasks (301-308) requiring a plurality of resources (101-103, 109-113), comprising the steps of

(a) constructing a set of constraints from given requirements of each task (301-308)and from given limitations on each resource (101-103, 109-113);

(b) determining for each task (301-308) a relative starting time, a relative ending time and an assignment of resources (101-103, 109-113), based on the constraints from said set;

(c) determining for each task (301-308)an absolute starting time, an absolute ending time and a collection of times and associated task processing speeds, based on the determined relative starting time, relative ending time and assignment of resources (101-103, 109-113) for said task, minimizing any violation of the constraints from said set; and

(d) determining the schedule (205), comprising for each task (301-308) the determined absolute starting time, absolute ending time, collection of times and associated task processing speeds and assignment of resources (101-103, 109-113) to said task.

2. A method as claimed in claim 1, where step (c) comprises

defining a sequence of windows (w₀ , . . . , w₁₅), a starting time of a window (w₀ , . . . , w₁₅) from said sequence corresponding to one of the relative starting time and the relative ending time of a task (301-308), and an ending time of said window (w₀ , . . . , w₁₃) corresponding to a starting time of a next window (w₀ , . . . , W₁₅) in said sequence;

determining an absolute length of the windows (w₀ , . . . , w₁₃) from said sequence, minimizing any violation of the constraints from said set;

determining for each window (w₀ , . . . , w₁₅) a processing speed for each task (301-308) and creating for each task (301-308) a collection of times and associated task processing speeds based thereupon, minimizing any violation of the constraints from said set; and

determining for each task (301-308) the absolute starting time and the absolute ending time from the absolute length of the windows (w₀ , . . . , w₁₅).

3. A method as claimed in claim 1 or 2, further comprising the step of

determining whether any violation of the constraints has occurred, and if so,

determining at least one of a new relative starting time for a task (301-308), a new relative ending time for a task (301-308), and a new assignment of a resource (101-103,109-113) to a task (301-308);

and

executing step (c).

4. A method as claimed in claim 2, where the step of determining the absolute length of the windows (w₀ , . . . , w₁₅) from said sequence comprises solving a linear programming problem.

5. A method as claimed in claim 2 or 4, where the step of determining for each window (w₀ , . . . , w₁₅) a task processing speed for each task (301-308) comprises solving a linear programming problem.

6. A scheduler (100) for determining a schedule for executing a plurality of tasks (301-308) requiring a plurality of resources (101-103, 109-113), comprising

constructing means (201) for constructing a set of constraints from given requirements of each task (301-308) and from given limitations on each resource (101-103, 109-113);

ordering means (202) for determining for each task (301-308) a relative starting time, a relative ending time and an assignment of resources (101-103, 109-113), based on the constraints from said set;

timing means (203) for determining for each task (301-308) an absolute starting time, an absolute ending time and a collection of times and associated task processing speeds, based on the determined relative starting time, relative ending time and assignment of resources (101-103, 109-113) for said task (301-308), minimizing any violation of the constraints from said set; and

scheduling means (204) for determining the schedule, comprising for each task (301-308) the determined absolute starting time, absolute ending time, collection of times and associated task processing speeds and assignment of resources (101-103, 109-113) to said task (301-308).

7. A scheduler (100) as claimed in claim 6, where the timing means (203) are arranged to

define a sequence of windows (w₀ , . . . , w₁₅), a starting time of a window (w₀ , . . . , w₁₅) from said sequence corresponding to one of the relative starting time and the relative ending time of a task (301-308), and an ending time of said window (w₀ , . . . , w₁₃) corresponding to a starting time of a next window (w₀ , . . . , w₁₅) in said sequence;

determine an absolute length of the windows (w₀ , . . . , w₁₅) from said sequence, minimizing any violation of the constraints from said set;

determine for each window (w₀ , . . . , w₁₅) a task processing speed for each task (301-308) and create for each task (301-308) a collection of times and associated task processing speeds based thereupon, minimizing any violation of the constraints from said set; and

determine for each task (301-308) the absolute starting time and the absolute ending time from the absolute length of the windows (w₀ , . . . , W₁₅).

8. A scheduler (100) as claimed in claim 6 or 7, being arranged to

determine whether any violation of the constraints has occurred, and if so, to

determine at least one of a new relative starting time for a task (301-308), a new relative ending time &

for a task (301-308), and a new assignment of a resource (101-103, 109-113) to a task (301-308); and

activate the timing means (203).

9. A scheduler (100) as claimed in claim 7, further comprising linear programming means (206) for solving a linear programming problem.

10. A system having a scheduler (100) as claimed in claim 6, 7, 8 or 9, and a plurality of resources (101-103, 109-113), the system being arranged to execute the tasks (301-308) on said plurality of resources (101-103, 109-113) according to the schedule (205) obtained from the scheduler (100).