A note on single-machine scheduling problems with position-dependent processing times

The purpose of this note is two-fold. First, it answers an open prob- lem about a single-machine scheduling problem with exponential position-dependent processing times de ned in [V. S. Gordon, C. N. Potts, V. A.Strusevich, J. D. Whitehead, Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation, Journal of Scheduling 11 (2008), 357{370]. In this problem, the processing time of job i when scheduled in rank r is equal to p(i; r) = pir-1,with a positive constant. Gordon et al show in the above-mentioned paper with priority-generating techniques that the problem of minimizing the total ow-time on one machine admits an O(n log n) algorithm when 2]0; 1[[[2;+1[, and leave the case 2 [1; 2[ open. We show that the problem admits an O(n log n) algorithm also for 2 [1; 2[. The second purpose of this note is to provide a simple and general insight on why and when position-dependent scheduling problems on one machine can be solved in time O(n log n).

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00647789
Author Moncel, Julien, Finke, Gerd, Jost, Vincent
Maintainer CCSD
Last Updated November 10, 2026, 21:57 (UTC)
Created November 10, 2026, 21:57 (UTC)
Identifier hal-00647789
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor LAAS-MOGISA ; Laboratoire d'analyse et d'architecture des systèmes (LAAS) ; Université Toulouse Capitole (UT Capitole) ; Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse) ; Institut National des Sciences Appliquées (INSA)-Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Institut National des Sciences Appliquées (INSA)-Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Université Toulouse - Jean Jaurès (UT2J) ; Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Université Toulouse III - Paul Sabatier (UT3) ; Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP) ; Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Université Toulouse Capitole (UT Capitole) ; Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse) ; Institut National des Sciences Appliquées (INSA)-Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Institut National des Sciences Appliquées (INSA)-Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Université Toulouse - Jean Jaurès (UT2J) ; Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Université Toulouse III - Paul Sabatier (UT3) ; Communauté d'universités et établissements de Toulouse (Comue de Toulouse)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP) ; Communauté d'universités et établissements de Toulouse (Comue de Toulouse)
creator Moncel, Julien
date 2011-12-02T00:00:00
harvest_object_id 844aa68f-81fa-40e3-aec1-9a7aaa445348
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2026-10-23T00:00:00
set_spec type:UNDEFINED