MAKESPAN MINIMIZATION ON IDENTICAL PARALLEL MACHINES SUBJECT TO MINIMUM TOTAL FLOW-TIME

ABSTRACT

We consider the problem of scheduling n jobs on m identical parallel machines. An optimal schedule to the proposed problem is defined as one that gives the smallest makespan (the completion time of the last job on any one of the parallel machines) among the set of all schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose two new simple heuristic algorithms and empirically compare their effectiveness and efficiency with several existing algorithms.

Keywords:

• Parallel machine scheduling
• hierarchical criteria
• makespan
• flowtime
• heuristic algorithms
• empirical results