Article ID: | iaor20114250 |
Volume: | 60 |
Issue: | 2 |
Start Page Number: | 301 |
End Page Number: | 315 |
Publication Date: | Jun 2011 |
Journal: | Algorithmica |
Authors: | Saks Michael, Divakaran Srikrishnan |
Keywords: | job shop, NP-hard, setup time |
We address the problem of sequential single machine scheduling of jobs with release times, where jobs are classified into types, and the machine must be properly configured to handle jobs of a given type. The objective is to minimize the maximum flow time (time from release until completion) of any job. We consider this problem under the assumptions of sequence independent set‐up times and item availability with the objective of minimizing the maximum flow time. We present an online algorithm that is