Minimizing the Total Weighted Flow-time of Jobs with Set-up Times and Unequal Release Dates: Application to Minimizing Maintenance Operations Cost

Kondo Hloindo Adjallah (1) , Kossi Pélopé Adzakpa (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

An efficient heuristic is proposed in this paper for solving the minimization problem of total weighted flow-time of n tasks or jobs while scheduling the tasks on parallel machines. The heuristic considers tasks with unequal release dates and set-up times characterized by the task sequences. For solving this problem, we designed an appropriate priority rule that locally optimizes task scheduling and minimizes their weighted flow-time. The Priority Rule for Total Weighted Flow-time with Set-ups Times (PRTWFST) is then used to design a real-time algorithm of tasks scheduling and allocation, with a complexity of O(n3). The algorithm is implemented for the scheduling and allocation of preventive maintenance tasks of a distributed system. Results of computational experimentation testify to the efficiency of the algorithm.

Mots clés: Scheduling; Maintenance; Flow-time; Weight; Setup time; Release date; Distributed system

Domaines: Recherche opérationnelle [math.OC]

Kondo Hloindo Adjallah, Kossi Pélopé Adzakpa. Minimizing the Total Weighted Flow-time of Jobs with Set-up Times and Unequal Release Dates: Application to Minimizing Maintenance Operations Cost. CESA'2003 Multiconference on Computational Engineering in Systems Applications with IMACS and IEEE/SMC, Jul 2003, Lille, France. pp.CD-ROM S3-R-00-0046: S3-FA-1-F1. ⟨hal-03091360⟩