Minimizing sum of completion times and makespan in master-slave systems

1

Minimizing Sum of Completion Times and Makespan in Master-Slave Systems
Joseph Y-T. Leung, Senior Member, IEEE, and Hairong Zhao, Member, IEEE

Abstract We consider scheduling problems in the master-slave model. In this model each job has to be processed sequentially in three stages. In the first stage, a preprocessing task runs on a master machine; in the second stage, a slave task runson a dedicated slave machine; and in the last stage, a postprocessing task again runs on a master machine, possibly different from the master machine in the first stage. It has been shown that the problem of minimizing the makespan or the sum of completion times is NP-hard in the strong sense even if preemption is allowed. In this paper we design efficient approximation algorithms to minimize the sumof completion times in various settings. These are the first general results for the minsum problem in the master-slave model. We also show that these algorithms generate schedules with small makespan as well. Index Terms Sequence and scheduling, approximation algorithms, makespan, linear programming

1 I NTRODUCTION We consider scheduling problems in the master-slave model which was recentlyintroduced by Sahni [21]. In this model, each job has to be processed sequentially in three stages. In the first stage, the preprocessing task runs on a master machine; in the second stage, the slave task runs on a dedicated slave machine; and in the last stage, the postprocessing task again runs on a master machine, possibly different from the master machine in the first stage. We use ai , bi and cito denote the preprocessing, slave and postprocessing tasks and task times of job i, respectively. We assume that ai > 0, bi > 0 and ci > 0. A job may have a release time ri ≥ 0, i.e., ai cannot start until time ri . In this paper, we assume that every job has a release time 0, unless stated otherwise. There are two cases when arbitrary release time is present. The first case deals with offlineproblems, i.e., the release times and processing times of all jobs are known in advance. The second case deals with online problems, i.e., we have no knowledge of a job i until it arrives at time ri , and when it arrives, we know everything about job i. We use the quadruple (ri , ai , bi , ci ) to denote job i. For simplicity, if ri = 0, we use the triplet (ai , bi , ci ) to represent job i. Eachmachine is either a master machine or a slave machine. The master machines are used to run preprocessing and/or postprocessing tasks, and the slave machines are used to run slave tasks, one slave machine for each slave task. In a single-master system, there is a single master to execute all preprocessing tasks (a tasks) and postprocessing tasks (c tasks). In a multi-master system, there are more thanone master, each of which is capable of processing both a tasks and c tasks. Finally, in some systems, there are distinct preprocessing masters (preprocessors) and postprocessing masters (postprocessors), which are used to process a tasks and c tasks, respectively. The master-slave model is closely related to the flow shop model. The system which has a single preprocessing master and a singlepostprocessing master can be seen as a two-machine flow shop with transfer lags ( [25] ). When there are more than one preprocessing and postprocessing masters, the model is a two-stage hybrid flow shop with transfer lags. Hybrid flow shop is often found in electronic
This work was partially supported by NSF Grant DMI-0300156. J. Y-T. Leung is with the Department of Computer Science, New Jersey Instituteof Technology (NJIT), Newark, NJ 07102. Email: leung@cis.njit.edu. H. Zhao is with the Department of Mathematics, Computer Science, & Statistics, Purdue University Calumet, Hammond, Indiana 46323. Email: hairong@calumet.purdue.edu.

2

manufacturing environment such as IC packaging and make-to-stock wafer manufacturing. In recent years, hybrid flow shop has received significant attention,...