Citation
A polynomial time OPT-1 algorithm for a scheduling problem with two delivery dates and cumulative payoffs. In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium, pages 268-289, 2013.
Paper
Abstract
We consider a single machine scheduling problem with two common delivery dates and unequal release dates for the jobs. The goal is to maximize the cumulative number of jobs processed before each delivery date. The general problem (with K ? 2 delivery dates) results from a practical situation in book digitization. The two delivery dates case considered here is weakly NP-hard. In this paper, we show for this problem a polynomial time algorithm with an absolute guarantee of 1. By considering the two delivery dates problem, this paper lays the basis for an approximation algorithm for the general K delivery dates problem.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2013-268-289-P, author = {Y. Seddik and C. Gonzales and S. Kedad-Sidhoum},
title = {A polynomial time OPT-1 algorithm for a scheduling problem with two delivery dates and cumulative payoffs},
booktitle = {In proceedings of the 6th Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2013), 27 - 30 Aug 2013, Ghent, Belgium},
year = {2013},
editor = {G. Kendall and B. McCollum and G. {Venden Berghe}},
pages = {268--289},
note = {Paper},
abstract = {We consider a single machine scheduling problem with two common delivery dates and unequal release dates for the jobs. The goal is to maximize the cumulative number of jobs processed before each delivery date. The general problem (with K ? 2 delivery dates) results from a practical situation in book digitization. The two delivery dates case considered here is weakly NP-hard. In this paper, we show for this problem a polynomial time algorithm with an absolute guarantee of 1. By considering the two delivery dates problem, this paper lays the basis for an approximation algorithm for the general K delivery dates problem.},
owner = {Graham},
timestamp = {2017.01.16},
webpdf = {2013-268-289-P.pdf} }