A branch and bound algorithm for single-machine production scheduling integrated with preventive maintenance planning

This paper deals with an integrated optimisation model for production scheduling and preventive maintenance (PM) in a single machine with its time to failure subject to a Weibull probability distribution. The objective is to minimise the total expected weighted completion time of jobs. To solve this problem, we develop a branch and bound (B&B) algorithm (hereafter called the B&BA). Several lower bounds, dominance rules and upper bounds are developed to enhance the performance of the B&BA. Extensive computational experiments on randomly generated problems with different configurations are conducted and the results show that the proposed method can find optimal solutions for problems with up to 18 jobs in a reasonable amount of computation time.