Parallel machine scheduling with limited controllable machine availability

Abstract

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.

Keywords:

• parallel machine scheduling
• controllable availability
• column generation
• branch and bound

Acknowledgements

The work presented in this paper has been supported by grants from the National High-Tech Research and Development Program (863 Program) of China (2008AA04Z104), National Natural Science Foundation of China (70871077), and ‘Shu Guang’ project (No. 09SG17) of Shanghai Municipal Education Commission and Shanghai Education Development Foundation.