Differential approximation analysis of Jackson's rule for single-machine scheduling problem with a fixed non-availability interval

In this paper, we consider the single machine scheduling problem with a fixed non-availability interval. The objective is to minimize the makespan. Our work aims at the comparison of Jackson's schedule to the optimal and the worst solutions in order to establish the differential approximation r...

Full description

Saved in:
Bibliographic Details
Main Authors: Kacem, I., Nagih, A., Seifaddini, M.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Approximation algorithms
Approximation methods
Educational institutions
Minimization
Schedules
Single machine scheduling
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we consider the single machine scheduling problem with a fixed non-availability interval. The objective is to minimize the makespan. Our work aims at the comparison of Jackson's schedule to the optimal and the worst solutions in order to establish the differential approximation ratio for this problem. The analysis of Jackson's rule shows that this rule cannot yield a constant differential approximation in the general case.
DOI:10.1109/ICNSC.2013.6548769