A Single Machine Scheduling Problem with Position-Dependent Processing Times and Precedence Constraints

Abstract : In many real-life situations the processing conditions in scheduling models cannot be viewed as given constants since they vary over time thereby affecting actual durations of jobs. We consider single machine scheduling problems of minimizing the makespan in which the processing time of a job depends on its position (with either cumulative deterioration or exponential learning). It is often found in practice that some products are manufactured in a certain order implied, for example, by technological, marketing or assembly requirements. This can be modeled by imposing precedence constraints on the set of jobs. We consider scheduling models with positional deterioration or learning under precedence constraints that built up iteratively from prime partially ordered sets of width bounded by some fixed value (this class of precedence constraints includes, in particular, series-parallel precedence constraints). We show that objective functions of the considered problems satisfy job module property and possess the recursion property. As a result, the problems under consideration are solvable in polynomial time
Type de document :
Rapport
2009
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00679814
Contributeur : Florent Breuil <>
Soumis le : vendredi 16 mars 2012 - 13:43:56
Dernière modification le : dimanche 28 janvier 2018 - 15:22:05

Identifiants

  • HAL Id : emse-00679814, version 1

Citation

Alexandre Dolgui, Valery Gordon, Vitaly Strusevich. A Single Machine Scheduling Problem with Position-Dependent Processing Times and Precedence Constraints. 2009. 〈emse-00679814〉

Partager

Métriques

Consultations de la notice

110