Search

This paper considers the problem of scheduling n independent jobs on m identical parallel machines in order to minimize the number of tardy jobs (ηT) considering the periodic preventive maintenance to avoid machine breakdowns. It assumes that there are several maintenance periods during the scheduling process and that each maintenance time is scheduled after a working time interval. Job preemption is not allowed. In this regard, a heuristic procedure and a mathematical model are proposed to minimize ηT. The S-B-C 1 heuristic is used to tackle the identical parallel machine scheduling problem. The suggested heuristic follows several steps to solve the problem. It depends on scheduling jobs with several batches based on the working time interval, where the total processing time of jobs for each batch should not exceed the working time interval. The first step uses the S-B-C 1 heuristic to determine the initial schedule for minimizing ηT. The second step calculates the slack time for each working time interval for each machine, which equals to the unscheduled time in the batch. Then, the tardy jobs are rescheduled in the system to minimize ηT considering scheduling jobs during the slack time for each batch. The results obtained show the effectiveness of the proposed heuristic to minimize ηT subject to periodic maintenance requirements. The heuristic procedure results show that the heuristic is able to find the optimal solution in 19 out of 54 instances. In the remaining cases, the ηT increases on the average 8.43%.