𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Loading Time Scheduling Problem

✍ Scribed by Randeep Bhatia; Samir Khuller; Joseph (Seffi) Naor

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
226 KB
Volume
36
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

The quay crane scheduling problem with t
The quay crane scheduling problem with time windows
✍ Frank Meisel πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 500 KB

The quay crane scheduling problem consists of scheduling tasks for loading and unloading containers on cranes that are assigned to a vessel for its service. This article introduces a new approach for quay crane scheduling, where the availability of cranes at a vessel is restricted to certain time wi

Solving the open shop scheduling problem
Solving the open shop scheduling problem
✍ Ulrich Dorndorf; Erwin Pesch; ToΓ n Phan-Huy πŸ“‚ Article πŸ“… 2001 πŸ› Springer US 🌐 English βš– 128 KB

Only few exact solution methods are available for the open shop scheduling problem. We describe a branch-and-bound algorithm for solving this problem which performs better than other existing algorithms. The key to the e ciency of our algorithm lies in the following approach: instead of analysing an

Human and machine effects in a just-in-t
Human and machine effects in a just-in-time scheduling problem
✍ Tamer Eren πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 64 KB

## Abstract In this article, single‐machine scheduling problems with learning effects of setup and removal times and deterioration effects of processing time are considered. The objective function of the problem is minimization of the weighted sum of total earliness and total tardiness. To get an e