Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems

Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor1999151
Country: Netherlands
Volume: 90
Issue: 2
Start Page Number: 214
End Page Number: 226
Publication Date: Apr 1996
Journal: European Journal of Operational Research
Authors: ,
Keywords: job shop, flowshop
Abstract:

Resource-constrained scheduling problems with a fixed number of task types are considered in which, in addition, either the processing times are bounded or the number of processors is fixed. For problems with makespan, (weighted) mean flow time, weighted number of tardy tasks, and sum of tardiness as objective functions polynomial time algorithms are presented. These algorithms generalize results derived by Blażewicz et al. for makespan problems and solve open problems listed by Hoogeveen et al. Furthermore, results for shop problems with multiprocessor tasks and unit processing times, in which either the number of jobs or the number of stages is fixed, are derived.

Reviews

Required fields are marked *. Your email address will not be published.