A heuristic algorithm for minimizing maintenance workforce level

packing Abstract. We develop a heuristic algorithm for minimizing the workforce level required to accommodate all the main-tenance jobs requested within a speci c time interval. Each maintenance job has its own release and due dates as well as the required man-days, and must be scheduled in a non-interrupted time interval, i.e. without preemption. However, the duration of each job is not xed, but to be determined within a speci c range. We show that this problem can be seen as a variant of the two-dimensional bin-packing problem with some additional constraints. We develop a non-linear mixed integer programming model for the proposed problem, and employ some well-known bin-packing algorithms to develop an e cient heuristic algorithm. In order to evaluate the performance of the proposed heuristic, we present a compu-tationally e cient scheme for getting a good lower bound for the actual minimum. The computational experiment shows that the proposed heuristic algorithm performs quite satisfactorily in practice