Scheduling heterogeneous partitioned resources with sharing constraints

• US 8,392,926 B2
• Filed: 04/06/2010
• Issued: 03/05/2013
• Est. Priority Date: 04/06/2010
• Status: Active Grant

• Current Assignee: Utopus Insights, Inc. (Vestas Wind Systems A/S)
• Original Assignee: International Business Machines Corporation
• Inventors: Kimbrel, Tracy J., Kumar, Tarun, McKenzie, Kevin D., Sviridenko, Maxim, Tomkowid, Debra, Prewitt, Richard D. Jr.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US12/755,089
• Publication Number:
  US 20110246994A1
• Time in Patent Office: 1,064 Days
• Field of Search: None
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• 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/10 Office automation; Time management

Abstract

A system and method that provides an automated solution to obtaining quality scheduling for users of computing resources. The system, implemented in an enterprise software test center, collects information from test-shop personnel about test machine features and availability, test jobs, and tester preferences and constraints. The system reformulates this testing information as a system of constraints. An optimizing scheduling engine computes efficient schedules whereby all the jobs are feasibly scheduled while satisfying the users'"'"' time preferences to the greatest extent possible. The method and system achieves fairness: if all preferences can not be meet, it is attempted to evenly distribute violations of preferences across the users. The test scheduling is generated according to a first application of a greedy algorithm that finds an initial feasible assignment of jobs. The second is a local search algorithm that improves the initial greedy solution.

Claims

1. A method for scheduling jobs to run on one or more computing resources, said method comprising:

receiving data specifying a configuration and availability of said one or more computing resources, one or more said computing resources M_i being partitionable into sub-units;

receiving data including users specified tasks, and expected durations of said specified tasks to run on said one or more said computing resources or sub-units thereof, a user task characterized as having an associated high priority level or regular priority level, and for each task, receiving data representing a set of positive preferences indicating user preferred time slots for processing said task, and data representing a set of negative user preferences indicating time slots for not processing said task;

assigning, based on said data and machines availability, users tasks to computing resources, computing resource sub-units, and time slots; and

generating a first initial schedule based on said assignments to provide, for a time horizon, and for one or more sub time intervals thereof, what task is scheduled, for which user the task is scheduled for, and a duration of the assigned task to be performed, said generating including scheduling as many high priority level jobs first, and then to schedule as many regular priority level jobs as possible, said first initial schedule including tasks that remain unassigned;

applying to said first initial schedule a local improvements optimization that assigns user tasks to computing resources sub-units and time slots, said assigning accounting for user preferences for said resources and time slots such that a total number of time slot assignments for users indicating said positive preference time slots is maximized, and a total number of time slot assignments for users indicating said negative preference time slots is minimized; and

generating a final task schedule based on said applied local improvements.

2. The method as claimed in claim 1 wherein a user task includes an associated sharing constraint, said sharing constraint including:

non-sharing wherein a computing resource can not execute other tasks concurrently;

computing resource-sharing wherein a computing resource is configured to concurrently run tasks that occupy different sub-units within that computing resource;

or

computing resource sub-unit-sharing, wherein sub-unit-sharing tasks can be processed on the same computing resource sub-unit concurrently up to a pre-determined maximum number of concurrent tasks, said configuration information specifying a configuration defined in relation to a task'"'"'s constraints.

3. The method as claimed in claim 2, wherein said generating said first initial schedule comprises:

a) entering a first loop L1 in which a task in the assigned order is traversed; and

,

b) within first loop L1, for each task, entering a second loop L2 that iterates through remaining computing resource-time slot pairs (M_i;

t) for determining whether to schedule said task in a remaining computing resource-time slot pair (M_i;

t), wherein, for a task to be scheduled, given a partial first initial schedule and a computing resource-time pair (M_i, t), choosing one or more computing resource sub-units of said computing resource M_i such that all sharing constraints for all tasks in said chosen computing resource sub-units are satisfied during the times t, . . . , t+p_j−

1, where p_j is a processing time for said task to be scheduled; and

,

c) assigning said task to one or more available computing resource sub-units of said computing resource M_i with a largest number of sub-unit-sharing tasks that are already assigned on prior iterations; and

,

d) repeating steps a) through b) to generate said first initial schedule.

4. The method as claimed in claim 3, wherein a user task that can not be scheduled in a computing resource-time slot pair (M_i;

t) is further included in said schedule as an unassigned task.

5. The method as claimed in claim 2, wherein said

minimizing a total number of time slot assignments for users indicating said negative preference time slots comprises:

bringing all users to a bound on maximum number of said negative preference time slots;

minimizing the number of users with this number of said negative preference time slots, and

said maximizing the total number of time slot assignments for users indicating said positive preference time slots comprises;

raising a minimum number of said positive preference time slots over all users, and, minimizing a number of users at this minimum level.

6. The method as claimed in claim 2, wherein said applying said local improvements optimization comprises:

a) selecting, from said first initial schedule, one or more task(s) that is(are) either not scheduled or scheduled in a non-preferred time slot associated with a negative or neutral task preference;

b) selecting one or more arbitrary additional tasks that are scheduled;

c) removing said selected tasks from the first initial schedule;

d) choosing a set of permutations of said selected tasks, and, for each permutation set of selected tasks;

generating a current task schedule based on said tasks of said chosen permutations set; and

,

comparing an objective measure of said generated current task schedule with a prior objective measure determined for a generated current task schedule associated with an immediate prior permutation of said selected tasks set; and

,

e) assigning said current task schedule as said final task schedule if said objective measure of said generated current task schedule is greater than said prior objective measure determined for a generated current task schedule associated with said immediate prior chosen task set permutation.

7. The method as claimed in claim 6, wherein said step d) further comprises:

identifying, for each task of said chosen permutations set, a most preferred available time slot, and temporarily assigning said task to said preferred available time slot to generate a current task schedule; and

,

computing said objective measure of said generated current task schedule.

8. The method as claimed in claim 6, wherein if said objective measure of said generated current task schedule is not greater than said prior objective measure determined for a generated current task schedule associated with an immediate prior chosen task set permutation, then choosing another permutation of said selected tasks, and repeating said steps d) and e) for said another permutation.

9. The method as claimed in claim 8, further comprising:

determining whether all permutations of said selected tasks have been processed; and

, if all permutations of said selected tasks have been processed;

determining whether other one or more arbitrary additional tasks that are scheduled can be considered for selection; and

, if one or more arbitrary additional tasks that are scheduled can be considered for selection, one of;

repeating steps b) though e).

10. The method as claimed in claim 9, wherein if one or more arbitrary additional tasks that are scheduled can not be considered for selection, then:

selecting, from said first initial schedule, other one or more task(s) that is(are) either not scheduled or scheduled in a non-preferred time slot; and

,

repeating steps b) though e).

11. The method as claimed in claim 6, wherein said objective measures are compared according to a priority order.

12. A system for scheduling jobs to run on one or more computing resources, said system comprising:

a memory device; and

a processor connected to the memory device, wherein the processor performs step of;

receiving data specifying a configuration and availability of said one or more computing resources, one or more said computing resources M_i being partitionable into sub-units;

receiving data including users specified tasks, and expected durations of said specified tasks to run on said one or more said computing resources or sub-units thereof, a user task characterized as having an associated high priority level or regular priority level, and for each task, receiving data representing a set of positive preferences indicating user preferred time slots for processing said task, and data representing a set of negative user preferences indicating time slots for not processing said task;

assigning, based on said data and machines availability, users tasks to computing resources, computing resource sub-units, and time slots; and

generating a first initial schedule based on said assignments to provide, for a time horizon, and for one or more sub time intervals thereof, what task is scheduled, for which user the task is scheduled for, and a duration of the assigned task to be performed, said generating including scheduling as many high priority levels first, and then to schedule as many regular priority level jobs as possible, said first initial schedule including tasks that remain unassigned;

applying to said first initial schedule a local improvements optimization that assigns user tasks to computing resources sub-units and time slots, said assigning accounting for user preferences for said resources and time slots such that a total number of time slot assignments for users indicating said positive preference time slots is maximized, and a total number of time slot assignments for users indicating said negative preference time slots is minimized; and

generating a final task schedule based on said applied local improvements.

13. The system as claimed in claim 12, wherein a user task includes an associated sharing constraint, said sharing constraint including:

non-sharing wherein a computing resource can not execute other tasks concurrently;

computing resource-sharing wherein a computing resource is configured to concurrently run tasks that occupy different sub-units within that computing resource;

or

computing resource sub-unit-sharing, wherein sub-unit-sharing tasks can be processed on the same computing resource sub-unit concurrently up to a pre-determined maximum number of concurrent tasks, said configuration information specifying a configuration defined in relation to a task'"'"'s constraints.

14. The system as claimed in claim 13, wherein said generating said first initial schedule comprises:

entering a first loop L1 in which a task in the assigned order is traversed; and

,

within first loop L1, for each task, entering a second loop L2 that iterates through remaining computing resource-time slot pairs (M_i;

t) for determining whether to schedule said task in a remaining computing resource-time slot pair (M_i;

t), wherein, for a task to be scheduled, given a partial first initial schedule and a computing resource-time pair (M_i, t), choosing one or more computing resource sub-units of said computing resource M_i such that all sharing constraints for all tasks in said chosen computing resource sub-units are satisfied during the times t, . . . , t+p_j−

1, where p_j is a processing time for said task to be scheduled; and

,

assigning said task to one or more available computing resource sub-units of said computing resource M_i with a largest number of sub-unit-sharing tasks that are already assigned on prior iterations; and

,

repeating entering said first L1 and second L2 loops to generate said first initial schedule.

15. The system as claimed in claim 14, wherein a user task that can not be scheduled in a computing resource-time slot pair (M_i;

t) is further included in said schedule as an unassigned task.

16. The system as claimed in claim 13, wherein said:

minimizing a total number of time slot assignments for users indicating said negative preference time slots comprises;

bringing all testers users to a bound on maximum number of said negative preference time slots; and

minimizing the number of users with this number of said negative preference time slots, and

said maximizing the total number of time slot assignments for users indicating said positive preference time slots comprises;

raising a minimum number of said positive preference time slots over all users, and, minimizing a number of users at this minimum level.

17. The system as claimed in claim 13, wherein said applying said local improvements optimization comprises:

selecting, from said first initial schedule, one or more task(s) that is(are) either not scheduled or scheduled in a non-preferred time slot associated with a negative or neutral task preference;

selecting one or more arbitrary additional tasks that are scheduled;

removing said selected tasks from the first initial schedule;

choosing a set of permutations of said selected tasks, and, for each permutation set of selected tasks;

generating a current task schedule based on said tasks of said chosen permutations set; and

,

comparing an objective measure of said generated current task schedule with a prior objective measure determined for a generated current task schedule associated with an immediate prior permutation of said selected tasks set; and

,

assigning said current task schedule as said final task schedule if said objective measure of said generated current task schedule is greater than said prior objective measure determined for a generated current task schedule associated with said immediate prior chosen task set permutation.

18. The system as claimed in claim 17, wherein for each permutation set of selected tasks:

identifying, for each task of said chosen permutations set, a most preferred available time slot, and temporarily assigning said task to said preferred available time slot to generate a current task schedule; and

,

computing said objective measure of said generated current task schedule,

wherein if said objective measure of said generated current task schedule is not greater than said prior objective measure determined for a generated current task schedule associated with an immediate prior chosen task set permutation, then choosing another permutation of said selected tasks, and repeating said steps of choosing a set of permutations and said assigning.

19. A computer program product for scheduling tests to run on one or more computing resources, the computer program product comprising:

a compute-readable storage medium having computer readable program code embodied therewith, the computer-readable program code comprising;

computer readable program code configured to;

receive data specifying a configuration and availability of said one or more computing resources, one or more said computing resources M_i being partitionable into sub-units;

receive data including users specified tasks, and expected durations of said specified tasks to run on said one or more said computing resources or sub-units thereof, a user task characterized as having an associated high priority level or regular priority level, and for each task, receive data representing a set of positive preferences indicating user preferred time slots for processing said task, and data representing a set of negative user preferences indicating time slots for not processing said task;

assign, based on said data and machines availability, users tasks to computing resources, computing resource sub-units, and time slots; and

generate a first initial schedule based on said assignments to provide, for a time horizon, and for one or more sub time intervals thereof, what task is scheduled, for which user the task is scheduled for, and a duration of the assigned task to be performed, said generating including scheduling as many high priority level jobs first, and then to schedule as many regular priority, level jobs as possible, said first initial schedule including tasks that remain unassigned;

apply to said first initial schedule a local improvements optimization that assigns user tasks to computing resources sub-units and time slots, said assigning accounting for user preferences for said resources and time slots such that a total number of time slot assignments for users indicating said positive preference time slots is maximized, and a total number of time slot assignments for users indicating said negative preference time slots is minimized; and

generate a final task schedule based on said applied local improvements.

20. The computer program product as claimed in claim 19, wherein a user task includes an associated sharing constraint, said sharing constraint including:

non-sharing wherein a computing resource can not execute other tasks concurrently;

computing resource-sharing wherein a computing resource is configured to concurrently run tasks that occupy different sub-units within that computing resource;

or

computing resource sub-unit-sharing, wherein sub-unit-sharing tasks can be processed on the same computing resource sub-unit concurrently up to a pre-determined maximum number of concurrent tasks, said configuration information specifying a configuration defined in relation to a task'"'"'s constraints.

21. The computer program product as claimed in claim 20, wherein said generating said first initial schedule comprises:

entering a first loop L1 in which a task in the assigned order is traversed; and

,

within first loop L1, for each task, entering a second loop L2 that iterates through remaining computing resource-time slot pairs (M_i;

t) for determining whether to schedule said task in a remaining computing resource-time slot pair (M_i;

t), wherein, for a task to be scheduled, given a partial first initial schedule and a computing resource-time pair (M_i, t), choosing one or more computing resource sub-units of said computing resource M_i such that all sharing constraints for all tasks in said chosen computing resource sub-units are satisfied during the times t, . . . , t+p_j−

1, where p_j is a processing time for said task to be scheduled; and

,

assigning said task to one or more available computing resource sub-units of said computing resource M_i with a largest number of sub-unit-sharing tasks that are already assigned on prior iterations; and

,

repeating entering said first L1 and second L2 loops to generate said first initial schedule.

22. The computer program product as claimed in claim 20, wherein said applying said local improvements optimization comprises:

selecting, from said first initial schedule, one or more task(s) that is(are) either not scheduled or scheduled in a non-preferred time slot associated with a negative or neutral task preference;

selecting one or more arbitrary additional tasks that are scheduled;

removing said selected tasks from the first initial schedule;

choosing a set of permutations of said selected tasks, and, for each permutation set of selected tasks;

generating a current task schedule based on said tasks of said chosen permutations set; and

,

comparing an objective measure of said generated current task schedule with a prior objective measure determined for a generated current task schedule associated with an immediate prior permutation of said selected tasks set; and

,

assigning said current task schedule as said final task schedule if said objective measure of said generated current task schedule is greater than said prior objective measure determined for a generated current task schedule associated with said immediate prior chosen task set permutation.