An Online Algorithm for a Problem in Scheduling with Set‐ups and Release Times

An Online Algorithm for a Problem in Scheduling with Set‐ups and Release Times

0.00 Avg rating0 Votes
Article ID: iaor20114250
Volume: 60
Issue: 2
Start Page Number: 301
End Page Number: 315
Publication Date: Jun 2011
Journal: Algorithmica
Authors: ,
Keywords: job shop, NP-hard, setup time
Abstract:

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 O(1)‐competitive, that is, always gets within a constant factor of optimal. We also show that exact offline optimization of maximum flow time is NP‐hard.

Reviews

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