An enhanced formulation and simple heuristic for scheduling jobs on unrelated parallel machines

Abstract

In this paper, we consider the scheduling problem that sequences a given set of independent jobs on unrelated parallel machines to minimize the mean flow time of these jobs. A parameter programming model using 0–1 integer variables is introduced, where the number of variables is reduced and converted into linear programming. In addition, an efficient and simple heuristic procedure is developed to solve this difficulty problem. The jobs are first scheduled by shortest processing time rule, the sequence of jobs on machines is then determined by comparing the increased flow time. An example is used for the illustration and computational experiments are performed to demonstrate the effectiveness of the heuristic algorithm.

Keywords:

• Scheduling
• unrelated parallel machines
• flow time
• heuristic