Minimizing mean flowtime and makespan on masterslave systems
The masterslave scheduling model is a new model recently introduced by Sahni. It has many important applications in parallel computer scheduling and industrial settings such as semiconductor testing, machine scheduling, etc. In this model each job is associated with a preprocessing task, a slave task and a postprocessing task that must be executed in this order. While the preprocessing and postprocessing tasks are scheduled on the master machine, the slave tasks are scheduled on the slave machines. In this paper, we consider scheduling problems on single-master masterslave systems. We first strengthen some previously known complexity results for makespan problems, by showing them to be strongly NP-hard. We then show that the problem of minimizing the mean flowtime is strongly NP-hard even under severe constraints. Finally, we propose some heuristics for the mean flowtime and makespan problems subject to some constraints, and we analyze the worst-case performance of these heuristics.
mean flowtime makespan masterslave systems scheduling np-hard heuristics