Scheduling resources in a penalty-based environment

A method for solving a problem, the method comprising:

• identifying a plurality of tasks to be assigned to one or more resources, wherein each job of a plurality of jobs includes multiple tasks ordered by chain precedence, wherein the plurality of jobs include active jobs and queued jobs, and wherein the plurality of tasks are associated with the active jobs;
• and
• assigning resources including start times for the plurality of tasks, using a processor, such that expected penalties for completion times of the plurality of tasks are reduced, wherein assigning the resources including start times for the plurality of tasks comprises:
• assigning a time period to an allocated think time partition in a time slot for each active job, wherein each time slot of a plurality of time slots comprises a plurality of allocated think time partitions corresponding to the active jobs;
• performing immediate assignments of resources for the plurality of jobs based on expected execution times of tasks by executing an initial algorithm to form a preliminary solution for scheduling the plurality of jobs;
• responsive to performing the immediate assignments, simulating random assignments for the plurality of jobs by executing a randomized algorithm to form a plurality of simulations for a duration of the time period assigned to the allocated think time partition to determine a probable best solution for scheduling the plurality of jobs, and wherein the probable best solution is calculated for each allocated think time partition;
• executing one of the initial algorithm and the randomized algorithm to assign resources for the completion of the plurality of tasks based on whether the initial algorithm or the randomized algorithm produced a best solution;
• responsive to identifying a job with a priority level that is greater than any of the active jobs, performing assignments and reassignments for the plurality of jobs;
• simulating random assignments for the plurality of jobs by executing a randomized algorithm to form a plurality of simulations;
• retaining a random seed value from the plurality of simulations, the random seed value that generates a current best random solution for scheduling the plurality of jobs using the randomized algorithm, wherein the random seed value is initialized to zero to indicate that the preliminary solution is the current best random solution, and wherein the random seed value is updated in response to executing the randomized algorithm additional times and finding a better solution than the current best random solution;
• determining whether a best solution was found using the initial algorithm or the randomized algorithm;
• responsive to the best solution being found using the initial algorithm, executing the initial algorithm and assigning resources based on results of the initial algorithm;
• and
• responsive to the best solution being found using the randomized algorithm, executing the randomized algorithm using the random seed value and assigning resources based on results of the randomized algorithm.

An apparatus, in a data processing system, for resource allocation of a plurality of tasks carrying penalties based on their completion time, the apparatus comprising:

• a bus;
• a set of storage devices operably connected to the bus, the set of storage devices storing program code;
• and
• a processor running a scheduler and operably connected to the bus, wherein the processor is configured to execute the program code to:
• identify the plurality of tasks to be assigned to one or more resources, wherein each job of a plurality of jobs includes multiple tasks ordered by chain precedence, wherein the plurality of jobs include active jobs and queued jobs, and wherein the plurality of tasks are associated with the active jobs;
• and
• assign resources including start times for the plurality of tasks such that expected penalties for completion times of the plurality of tasks are reduced, wherein assigning the resources including start times for the plurality of tasks comprises:
• assigning a time period to an allocated think time partition in a time slot for each active job, wherein each time slot of a plurality of time slots comprises a plurality of allocated think time partitions corresponding to a plurality of active jobs;
• performing immediate assignments of resources for the plurality of jobs based on expected execution times of tasks by executing an initial algorithm to form a preliminary solution for scheduling the plurality of jobs;
• simulating, responsive to performing the immediate assignments, random assignments for the plurality of jobs by executing a randomized algorithm to form a plurality of simulations for a duration of the time period assigned to the allocated think time partition to determine a probable best solution for scheduling the plurality of jobs, and wherein the probable best solution is calculated for each allocated think time partition;
• and
• executing one of the initial algorithm and the randomized algorithm to assign resources for the completion of the plurality of tasks based on whether the initial algorithm or the randomized algorithm produced a best solution.

A computer program product for resource allocation of a plurality of tasks carrying penalties based on their completion time, the computer program product comprising:

• a set of storage devices;
• program code, stored on at least one of the set of storage devices, for identifying the plurality of tasks to be assigned to one or more resources, wherein each job of a plurality of jobs includes multiple tasks ordered by chain precedence, wherein the plurality of jobs include active jobs and queued jobs, and wherein the plurality of tasks are associated with the active jobs;
• and
• program code, stored on at least one of the set of storage devices, for assigning resources including start times for the plurality of tasks such that expected penalties for completion times of the plurality of tasks are reduced, wherein the program code for assigning the resources including start times for the plurality of tasks comprises:
• program code, stored on at least one of the set of storage devices, for assigning a time period to an allocated think time partition in a time slot for each active job, wherein each time slot of a plurality of time slots comprises a plurality of allocated think time partitions corresponding to the active jobs;
• program code for performing immediate assignments of resources for the plurality of jobs based on expected execution times of tasks by executing an initial algorithm to form a preliminary solution for scheduling the plurality of jobs;
• program code, stored on at least one of the set of storage devices, for responsive to performing the immediate assignments, simulating random assignments for the plurality of jobs by executing a randomized algorithm to form a plurality of simulations for a duration of the time period assigned to the allocated think time partition to determine a probable best solution for scheduling the plurality of jobs, and wherein the probable best solution is calculated for each allocated think time partition;
• program code, stored on at least one of the set of storage devices, for executing one of the initial algorithm and the randomized algorithm to assign resources for the completion of the plurality of tasks based on whether the initial algorithm or the randomized algorithm produced a best solution.