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 th

220 Journal of the Chinese Institute of Industrial Engineers, Vol. 21, No. 3, pp. 220-229 (2004)

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

Jatinder N. D. Gupta*

College of Administrative Science University of Alabama in Huntsville

Huntsville, AL 35899, USA

Johnny C. Ho

Department of Information and Decision Sciences University of Texas at El Paso, El Paso, TX 79968, USA

Alex J. Ruiz-Torres

Department of Industrial Engineering

Polytechnic University of Puerto Rico, San Juan, PR 00918, USA

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.

1. INTRODUCTION

The scheduling problem considered in this paper is described as follows: a set N = {1,2, ... , n} of n jobs available at time zero is to be processed on m identical parallel machines. Each job i∈N is to be processed without interruption on one of the m machines with processing time pi. Each machine can process only one job at a time and no job may be processed by more than one machine. Setup time, if any, is included in the processing time. It is desired to minimize the total flow-time as the primary objective and minimize makespan (maximum completion time) as the secondary objective. Thus, it is required to find a schedule for which the maximum completion time (makespan) is minimized, subject to the constraint that no reduction in the total flow-time is possible.

Following the three field notation of scheduling problems, the above identical parallel machine problem to minimize makespan subject to minimum total flowtime is represented as a P||F(Cmax/∑Ci)

h

the functional notation P||F(Cmax/∑Ci) designates

h

that we hierarchically minimize makespan subject to minimum total flowtime. This problem has been shown to be NP-hard by Bruno, Coffman and Sethi [1].

In view of the NP-hard nature of the problem, heuristic algorithms for its solution are developed by Coffman and Sethi [2]. Eck and Pinedo [5] improved the results of Coffman and Sethi [2] and proposed two heuristic methods for solving the P||F(Cmax/∑Ci)

h

problem. They also proved that one of their proposed heuristics for solving the P2||F(Cmax/∑Ci) problem

h

gives makespan that is guaranteed to be no more than 3.7037% above the makespan of the optimal schedule. Leung and Young [8] considered the preemptive case of the problem and developed an algorithm for its solution. Gupta and Ho [6] proposed a lexicographic search algorithm to find an optimal solution to solve

problem. To solve the the P2||F(Cmax/∑Ci)

h

P||F(Cmax/∑Ci)

h

problem, improved heuristic

problem where P designates the identical parallel machines, Cmax denotes the maximum completion time (makespan), ΣCi represents the total flowtime, and

algorithms based on the listfit concept are described and evaluated by Gupta and Ruiz-Torres [7].

This paper proposes two simple improvement heuristic algorithms to find an approximate solution to

*

Corresponding author: guptaj@uah.edu