Scheduling unit length jobs with parallel nested machine processing set restrictions

Scheduling unit length jobs with parallel nested machine processing set restrictions

0.00 Avg rating0 Votes
Article ID: iaor20071720
Country: United Kingdom
Volume: 33
Issue: 3
Start Page Number: 620
End Page Number: 638
Publication Date: Mar 2006
Journal: Computers and Operations Research
Authors: ,
Keywords: computational analysis
Abstract:

This article explores the impact of restricting the machines upon which individual jobs may be scheduled. Even the simple case of a single stage of identical parallel machines cannot be solved to optimality in a reasonable time. We therefore focus on the case when job processing times are identical. In some applications the machine processing sets of jobs are structured in a nested fashion and do not partially overlap. We present efficient algorithms for solving this nested problem to optimality for each of the standard scheduling objective functions. In particular, an algorithm with constant running time minimises makespan on a fixed number of machines regardless of the number of jobs. Improvements in efficiency have been gained by attention to implementation issues, thus challenging the conventional approach to evaluating complexity.

Reviews

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