Minimizing the number of late jobs in single machine scheduling with nested execution intervals

This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Job execution intervals are assumed to be nested each inside the other, like Russian dolls. The objective is to minimize the number of late jobs....

Full description

Saved in:
Bibliographic Details
Main Authors: Briand, C., Ourari, S., Bouzouia, B.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
dominance conditions
Dynamic programming
Heuristic algorithms
nested execution intervals
Polynomials
Single machine scheduling
Sufficient conditions
Uninterruptible power systems
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper considers the problem of scheduling n jobs on a single machine. A fixed processing time and an execution interval are associated with each job. Job execution intervals are assumed to be nested each inside the other, like Russian dolls. The objective is to minimize the number of late jobs. For this problem, denoted as 1|r i , nested| SigmaU i , a new dominance condition and an optimal O(n 3 ) solving procedure are proposed
ISSN:2161-1890
DOI:10.1109/ICSSSM.2006.320674