Uniform Machines Scheduling Problem With Periodic Maintenance

Scheduling problem has a wide range of application background,including the actual industrial production,transportation,communication network and other fields.In traditional scheduling problems,it is widely assumed that machines are available all the time.This assumption is reasonable when short-term scheduling environments are considered.However,if the machine does not rest,it may cause excessive wear and even safety accidents.In order to improve the service life of the machine and ensure the safety of the production environment,it is essential for the companies to develop an effective maintenance strategy.This thesis mainly studies three uniform-machine scheduling problems with periodic maintenance:The first one is the scheduling QmPM|pj=p|Cmax with equal processing time jobs to minimize the makespan.The scheduling problem is called P-problem,the exact solution can be obtained in polynomial time.We design the corresponding exact algorithms and optimal makespan functions for different cases.The second problem is the scheduling Q2PM|w≤T/3|Cmax with the objective to minimize the makespan.It shows that this problem is NP-hard.A mixed integer programming model is constructed to solve small sized and moderate sized instances and a heuristic LLM algorithm is proposed to solve large sized instances.It is showed that the worst-case bound of the heuristic algorithm LLM is at most 2.Finally,the superiority of LLM algorithm is verified by numerical experiments.The objective is minimizing the sum of completion times for the three scheduling problem Q2PM‖ΣCi.Firstly,it shows that this problem is NP-hard.A mixed integer programming model is constructed.Secondly,we summarize the properties of optimal scheduling,and propose a Maximum Last Load(MLL)optimization strategy and a heuristic algorithm ROPT.Finally,the superiority of ROPT algorithm is verified by numerical experiments.