Complexity analysis of energy-efficient single machine scheduling problems - Université de technologie de Troyes Accéder directement au contenu
Article Dans Une Revue Operations Research Perspectives Année : 2019

Complexity analysis of energy-efficient single machine scheduling problems

Résumé

This paper deals with the complexity analysis of several energy-oriented single-machine scheduling problems addressed in the literature. The considered machine may be in different states: OFF, ON, Idle, or in transitions between them. The energy consumption of the machine at each time-slot is state-dependent. The objective is the minimization of the total energy consumption costs over the planning horizon.For this purpose, two particular cases with constant energy price and increasing energy prices during all the time-slots are studied. These two problems are proved to be polynomial. Moreover, the general version of this problem with Time-Of-Use (TOU) energy prices and different processing times of the jobs is investigated in two versions: with and without the fixed sequence for the jobs. As the results, the version with the fixed sequence is proved to be polynomial, and the version without the fixed sequence (general version) is proved to be NP-hard.This paper also introduces different lower bounds to deal this general version of the problem. The performances of these lower bounds are discussed based on different numerical instances.
Fichier principal
Vignette du fichier
S2214716018301702.pdf (482.37 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02311194 , version 1 (22-10-2021)

Licence

Paternité - Pas d'utilisation commerciale

Identifiants

Citer

Mohammadmohsen Aghelinejad, Yassine Ouazene, Alice Yalaoui. Complexity analysis of energy-efficient single machine scheduling problems. Operations Research Perspectives, 2019, 6, pp.100105. ⟨10.1016/j.orp.2019.100105⟩. ⟨hal-02311194⟩
42 Consultations
42 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More