Ting Wang, Roberto Baldacci, Andrew Lim, Qian Hu*. A branch-and-price algorithm for scheduling of deteriorating jobs and flexible periodic maintenance on a single machine. European Journal of Operational Research. 2018, 271 (3): 826-838. DOI
In many production systems, maintenance activities including preventive maintenance, repairs and tool changes are periodically scheduled. The activities can revert the machine from a sub-normal processing rate to a normal one. We study a single machine scheduling problem where deteriorating jobs and flexible periodic maintenance are considered. In the problem, a single machine is operated to process a set of jobs with alternating processing periods and maintenance periods. In a processing period, a subset of jobs is sequentially processed and the completion time of the last job cannot exceed the allowed maximum duration. The actual processing time of each job grows at a linear job-specific deterioration rate and depends on its starting time within the period. Between two processing periods, a maintenance period with a fixed duration exists and the maintenance activities are carried out so that the processing rate of the machine is reverted to be normal. The objective is to schedule all the jobs to a set of processing periods and minimize the makespan of the schedule. The deterioration effect makes the problem to be complicated as nonlinear terms are introduced when calculating the actual processing times. We formulate the problem as a set-partitioning model and propose a branch-and-price algorithm to solve the problem exactly. A label-setting algorithm with a dominance rule is designed to solve the pricing problem in column generation. Computational experiments are conducted on a set of randomly generated test instances to evaluate the performance of the exact algorithm.
Computational experiments were conducted on a set of randomly generated instances to evaluate the performance of the branch-and-price algorithm. The algorithm was implemented using JAVA programming language and executed on a PC with an Intel(R) Core(TM) i7-6700 CPU clocked at 3.40 GHz and 16 GB RAM. The LP solver used was ILOG CPLEX 12.63 (64-bit Windows edition). The final results were obtained by executing the branch-and-price algorithm on all the test instances with a time limit of 3600 CPU seconds. The numeric tolerance is 0.001, because the makespan in the objective is generally evaluated by minutes or seconds in practice.