The Minimum Job Scheduling Problem

Description:

The Scheduling problem is a classified NP-hard optimization problem. It can be defined as:

Input:
-Set T of tasks {t₁,...t_n}.
-Number m of equal processors.

Output:
-An m-processor schedule for T.

Question

Given a set of tasks T with an execution time for each one, and a group of equal processors, find the task's allocation that minimizes the total execution time for the processors.

The total time of a group of processors is the longest time of all of them, because we consider that all the processors starts his execution threads at the same time, so the last processors that finishes his tasks is the one who delimits the total time of the group.

Problem Instances

In order to define an instance of this problem we need to provide the set of tasks, giving for each task his execution time. We also have to indicate the number of processors that will compound the group.

Related Bibliography and Papers