Parallel machine scheduling with limited controllable machine availability

摘要

Most machine scheduling models assume that either the machines are available all the time, or the time of their unavailability is fixed as a constraint. In this paper, we study the problem that neither the unavailability length nor the start time of machine unavailability is fixed. Instead, they would be determined in order to minimise the total cost involved with the completion time and the unavailable time. This model could represent a more realistic and complex situation, in which jobs and machines' availability operations should be optimised simultaneously. After the model is formulated, some properties of the problem are presented. Then a branch and bound algorithm based on column generation approach is proposed to solve the problem. The computation results show that, within a reasonable computation time, the proposed algorithm can solve medium sized problems optimally.