The Loading Time Scheduling Problem

Randeep Bhatia*, Samir Khuller, Joseph Naor

*Corresponding author for this work

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the set of machines. Each machine has a loading time that is incurred only for the first task that is scheduled on the machine in a particular run. This basic scheduling problem arises in the context of machining on numerically controlled machines and query optimization in databases and in other artificial intelligence applications. We give the first nontrivial approximation algorithm for this problem. We also prove nontrivial lower bounds on best possible approximation ratios for these problems. These improve on the nonapproximability results that are implied by the nonapproximability results for the shortest common supersequence problem. We use the same algorithm technique to obtain approximation algorithms for a problem arising in the context of code generation for parallel machines and for the weighted shortest common supersequence problem.

Original languageEnglish (US)
Pages (from-to)1-33
Number of pages33
JournalJournal of Algorithms
Volume36
Issue number1
DOIs
StatePublished - Jul 2000

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The Loading Time Scheduling Problem'. Together they form a unique fingerprint.

Cite this