An effective heuristic for the single-machine scheduling problem with flexible maintenance under human resource constraints

In this paper, we study a new scheduling problem that considers both production and flexible preventive maintenance on a single machine where the human resource constraints (the availability and the competence) are taken into account. The objective function involves both the tardiness and the earliness resulting from production and maintenance tasks. We propose a mathematical formulation of the studied problem that is expressed in the constraint programming (CP) paradigm as a set of linear constraints. This CP modeling had been implemented in ILOG OPL language and the exact method Cplex is applied on it to compute the optimal solutions of relatively small instances of the problem. Further, a heuristic algorithm is provided to deal with lager instances of the problem. Computational experiments demonstrate that the proposed heuristic performs well and is able to find good solutions to instances up to 700 jobs in a reasonable CPU time.