Lower bounds for total weighted completion scheduling problem with availability constraints

Cherif Sadfi (1) , Imed Kacem (2, 3) , Wei Liu

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 LITA - Laboratoire d'Informatique Théorique et Appliquée
3 LCOMS - Laboratoire de Conception, Optimisation et Modélisation des Systèmes

In this paper we consider the single machine total weighted completion scheduling problem with availability constraints. The machine is subject to many periods of maintenances. To solve this problem, we propose some lower bounds. A computational experiments and analysis are given afterwards to test the efficiency of the proposed lower bounds.

Keywords: Single machine scheduling; Dynamic programming; Optimal scheduling; Laboratories; Parallel machines; Heuristic algorithms; Availability; Processor scheduling; Testing; Integer linear programming; single machine; availability constraints; total weighted completion time; lower bound

Domains: Operations Research [cs.RO]

Cherif Sadfi, Imed Kacem, Wei Liu. Lower bounds for total weighted completion scheduling problem with availability constraints. Industrial Engineering (CIE39), Jul 2009, Troyes, France. pp.159-163, ⟨10.1109/ICCIE.2009.5223882⟩. ⟨hal-02496074⟩