Research On Parallel Machine Scheduling With Tool Replacement And Fixed Cycle Maintenance

Scheduling mainly researches the optimization of the tasks under the limited resource or constraints such as the given number of machines,workpieces,and time.In modern life,it is a type of important optimization issue.With the increasing complexity of modern production,there is a higher demand for the theory and application of scheduling.Efficient scheduling method is the key to win in the market in the market environment of pursuing efficiency.Scheduling is also extensively adopted in daily life,such as bus scheduling,computer process scheduling,airport scheduling,personnel scheduling and so on.Firstly,this paper describes the origin of periodic maintenance scheduling and the development of scheduling theory,summarizes the research status at home and abroad,and depicts the concept and representation of scheduling.The innovative work of this paper is to study two kinds of machine scheduling with tool replacement and fixed cycle maintenance machines.The first one is the scheduling with the goal function of minimizing the schedule length,which has equivalent maintenance time of machines with tool replacement and fixed cycle maintenance.Under the condition that the workpiece can not be interrupted,a 0-1 mathematical programming model with the same processing time and different processing time is provided.Based on the LPT algorithm,a heuristic algorithm SC is designed.In order to test the performance of the algorithm,a lower bound of the optimal schedule length is given by the water injection model.In the numerical experiments,it is found that the average error of the algorithm is less than 1% for 500 workpieces.The results show that the heuristic algorithm SC has more advantages in solving large-scale problems.The second one is the scheduling with machines of tool replacement and of fixed cycle maintenance,whose maintenance time is different and depends on machine load.The objective function is to minimize the scheduling time.Based on the parallel machine splicing,the maintenance interval as a box,each workpiece is assigned their own positions,four mathematical programming models are put out to solve small-scale scheduling cases.In order to solve large-scale scheduling cases,a heuristic algorithm LPT-JTF is designed based on the LPT algorithm and the allocation mechanism that each workpiece is first arranged to the earliest completed work-piece machine.Similarly,a lower bound of the optimal schedule length is offered by the water injection model.In the numerical experiments,it is found that the average error of the algorithm is less than 1% for 500 workpieces.The results show that the heuristic algorithm LPT-JTF is suitable for solving large-scale instances.