Preemptive scheduling with position costs

Authors

  • Francis Sourd LIP6 - CNRS - Université Paris

Keywords:

Scheduling algorithm, preemption, primal-dual algorithm, dynamic programming

Abstract

This paper is devoted to basic scheduling problems in which the scheduling cost of a job is not a function of its completion time. Instead, the cost is derived from the integration of a cost function over the time intervals on which the job is processed. This criterion is specially meaningful when job preemption is allowed. Polynomial algorithms are presented to solve some special cases including a one-machine problem with a common due date and a two-machine problem with linear nondecreasing cost functions.

Downloads

Published

2006-06-30

How to Cite

Sourd, F. (2006). Preemptive scheduling with position costs. Algorithmic Operations Research, 1(2). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/668

Issue

Vol. 1 No. 2 (2006)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.