Scheduling in MapReduce-like systems for fast completion time
A method and system for scheduling tasks is provided. A plurality of lower bound completion times is determined, using one or more computer processors and memory, for each of a plurality of jobs, each of the plurality of jobs including a respective subset plurality of tasks. A task schedule is determined for each of the plurality of processors based on the lower bound completion times.
1. A computer-implemented method for scheduling a plurality of tasks, wherein tasks are assigned respectively to one of a plurality of processors, the method comprising:
in response to respective arrivals of new jobs, determining, using one or more computer processors and memory, weighted lower bound completion times for a plurality of jobs respectively based on an importance of its respective job, wherein a job comprises a plurality of tasks; and
determining, using one or more computer processors and memory, a task schedule for the plurality of processors respectively based on a ranked order of the plurality of jobs ranked according to the weighted lower bound completion times to reduce a weighted sum of job completion times.
2. The method of claim 1 , further comprising scheduling, at the plurality of processors respectively, the tasks based on the task schedule.
3. The method of claim 1 , wherein determining the weighted lower bound completion times comprises:
solving a linear program to determine a lower bound completion time of a respective job in the plurality of jobs, wherein the linear program is determined by the equation
Z
LP
=
min
∑
j
∈
J
w
j
C
j
,
wherein Z LP is a minimum weighted completion time, j is the respective job in the plurality of jobs J, w j represents a job weight, and C j represents a calculated job completion time.
4. The method of claim 1 , further comprising:
determining the respective weighted lower bound completion times for jobs in the plurality of jobs at a predetermined time interval in response to a respective new job arrival during the predetermined time interval.
5. An apparatus for scheduling a plurality of tasks, wherein tasks are assigned respectively to one of a plurality of processors, the apparatus comprising one or more computer processors and memory, the one or more computer processors and memory configured to:
in response to respective arrivals of new jobs, determine weighted lower bound completion times for a plurality of jobs respectively based on an importance of its respective job, wherein a job comprises a plurality of tasks; and
determine a task schedule for the plurality of processors respectively based on a ranked order of the plurality of jobs ranked according to the weighted lower bound completion times to reduce a weighted sum of job completion times.
6. The apparatus of claim 5 , wherein the one or more computer processors and memory are further configured to:
schedule, at the plurality of processors respectively, the tasks based on the task schedule.
7. The apparatus of claim 5 , wherein the one or more computer processors and memory are further configured to:
solve a linear program to determine a lower bound completion time of a respective job in the plurality of jobs, wherein the linear program is determined by the equation
Z
LP
=
min
∑
j
∈
J
w
j
C
j
,
wherein Z LP is a minimum weighted completion time, j is the respective job in the plurality of jobs J, w j represents a job weight, and C j represents a calculated job completion time.
8. The apparatus of claim 5 , wherein the one or more computer processors and memory are further configured to:
determine the respective weighted lower bound completion time for jobs in the plurality of jobs at a predetermined time interval in response to a respective new job arrival during the predetermined time interval.
9. An article of manufacture including a tangible non-transitory computer-readable medium having instructions stored thereon, that in response to execution by a computing device cause the computing device to perform operations comprising:
in response to respective arrivals of new jobs, determining weighted lower bound completion times for a plurality of jobs respectively based on an importance of its respective job, wherein a job comprises a plurality of tasks; and
determining a task schedule for the plurality of processors respectively based on a ranked order of the plurality of jobs ranked according to the weighted lower bound completion times to reduce a weighted sum of job completion times.
10. The article of manufacture of claim 9 , wherein the operations further comprise scheduling, at the plurality of processors respectively, the tasks based on the task schedule.
11. The article of manufacture of claim 9 , wherein the operation of determining the weighted lower bound completion times comprises:
solving a linear program to determine a lower bound completion time of a respective job in the plurality of jobs, wherein the linear program is determined by the equation
Z
LP
=
min
∑
j
∈
J
w
j
C
j
,
wherein Z LP is a minimum weighted completion time, j is the respective job in the plurality of jobs J, w j , represents a job weight, and C j represents a calculated job completion time.
12. The article of manufacture of claim 9 , wherein the operation of determining the respective weighted lower bound completion times for jobs in the plurality of jobs is performed at a predetermined time interval in response to a respective new job arrival during the predetermined time interval.