Two Kinds Of Single Machine And Parallel Machine Scheduling Problems Research With Maintenance Requirements

Scheduling has been one of the most promising problems in the field of combinatorial optimization researches. Meanwhile, scheduling problems with maintenance considerations have attracted many researchers’ attention in the past few decades. In this paper, we mainly study two scheduling problems with maintenance.The first scheduling problem is a single-machine scheduling with a mandatory maintenance whose duration is workload-dependent, namely the duration of the maintenance is a nonnegative increasing function f of the workload that is scheduled to be carried by the machine before the maintenance. The start time of the machine maintenance is restricted to a time window[u, v],where 0 ￡u ￡v. The objective is to determine the start time of the maintenance and schedule all the jobs to the machine such that the maximum lateness is minimized. An approximation algorithm EDDMW based on the classical Earliest Due Date first rule is proposed. It is showed that the proposed algorithm is optimal for some special cases and that it has a tight bound for the scheduling problem under consideration.The second problem is a parallel-machine scheduling with tool changes and periodic availability constraint where 1m machines need tool changes and 1m -m machines are periodically unavailable, jobs are non-preemptive, and the objective is minimizing the makespan. To solve the problem, we establish a mixed 0-1 programming model and propose two sets of heuristic algorithms based on the classical algorithm LPT and LS. The basic idea behind the mathematical programming model is transforming the parallel machine setting into a single machine setting. Numerical experiments display that the model can deal instances within 10 jobs in reasonable computing times. Meanwhile, we provide a lower bound inspired by water model to facilitate the evaluation of the error ratios of the algorithms. We also conduct computational experiments which show that each of the heuristics can solve instances of 2000 items in one second on average with average relative error and maximum relative error less than 10% for each problem size. Accordingly, it provides an efficient algorithm for solving large scale problems.