MINIMISING THE COST OF SCHEDULING MAINTENANCE TASKS ON A SINGLE MACHINE

摘要

This paper deals with the problem of scheduling maintenance tasks for a single processor. The considered maintenance tasks have some characteristics: when a maintenance task completes before a first due date d_(i1) or after a second due date d_(i2), greater than d_(i1), the cost of the maintenance is greater to that when the task i is achieved in [d_(i1) , d_(i2)] interval. In other words, the maintenance task's cost is considered optimal if and only if its completion time is in [d_(i1), d_(i2)] interval. To solve optimally the problem, we develop in a first step a linear model. In a next step, we add to this model some valid inequalities in order to improve its linear relaxation objective function value and use it as lower bound in a branch and bound algorithm. Computational results are presented and analysed in the last part of this paper.