Preemptive Scheduling Problem And Optimal Algorithm On Non-simultaneously Available Parallel Machines

The production scheduling problem is an important part of the supply chain.It is very important to study the production scheduling problem and put forward the optimization algorithm and reasonable production scheduling strategy to enhance the competitiveness of production in the supply chain.Therefore,this thesis mainly studies the production scheduling problem on non-simultaneously available parallel machines.Among them,in the supply chain production enterprises,the use of conveyor belts,conveyors,packaging machines and other logistics machines to carry out production operations can be regarded as parallel machine production scheduling problems.By studying the reasonable matching of job and machine,to improve the production efficiency and profit in the supply chain.In order to minimize the maximum production completion time and the total processing cost of machine consumption,the corresponding optimal preemptive algorithms are given.At the beginning,this thesis briefly introduces the background,reality and significance of the research problem,as well as the relevant research problems of domestic and foreign scholars and the research content of this thesis.Secondly,considering that the machines in the production link of the supply chain do not have the time to prepare for maintenance,the light may cause the machine accuracy to be reduced,and the unqualified products will be produced in the production process;the production efficiency of the workpieces may be reduced due to the long-term processing wear of the machines;it may also cause machine failure and increase the maintenance cost;serious may cause safety accidents and bring great losses.Therefore,it is very important for the development of supply chain to consider increasing machine preparation time for preventive maintenance before the start of production scheduling.Aiming at the problem of traditional machine scheduling where all the machines are available simultaneously at time zero,this thesis mainly considers the preemptive production scheduling problem on non-simultaneously available parallel machines,including two variants of the problem,namely the identical-machine case and the uniform-machine case.Our goal is to minimize the maximum completion time,e.g.makespan.For the variant with m identical machines case,this thesis provides a polynomial time algorithm that finds an optimal schedule with at most m-1 preemptions.For the uniform-machine case,by introducing the concept of virtual machines,which first convert the real machines to virtual machines that guarantee that a machine with an earlier available time has a larger speed at any time.Then this thesis proposes a polynomial time algorithm that finds an optimal schedule with no more than m~2+3m/2-2 preemptions.Thirdly,in the production and manufacturing of the supply chain,reducing the total cost of machine consumption can improve the production profit of the supply chain.When considering the production of products,manufacturers also need to combine with the corresponding machine cost,so as to develop a more reasonable and suitable scheduling strategy for production enterprises.Therefore,preemptive production scheduling problem with machine processing cost on non-simultaneously available parallel machines is studied.The problem is that each machine has a unit processing cost on non-simultaneously available parallel machines,and the goal is to complete all tasks within a given delivery period to minimize the total processing cost.This thesis presents a polynomial-time preemptive optimal algorithm for identical machines case.