An online algorithm for a problem in scheduling with set-ups and release times

Srikrishnan Divakaran, Michael Saks

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)301-315
Number of pages15
JournalAlgorithmica (New York)
Volume60
Issue number2
DOIs
StatePublished - Jun 1 2011

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Analysis of algorithms
  • Approximation algorithms
  • Batch scheduling
  • Online algorithms
  • Operations research
  • Scheduling with set-ups

Fingerprint Dive into the research topics of 'An online algorithm for a problem in scheduling with set-ups and release times'. Together they form a unique fingerprint.

Cite this