Study On Scheduling Problem Of Two Parallel Machines With Mould Constraint

As a significant part of the real economy,manufacturing is an influential guarantee for maintaining the stable development of the country and society.China has been vigorously promoting the development of intelligent manufacturing.This also means that more efficient and scientific production scheduling is required to control the whole production process,especially for the high-tech,highly automated manufacturing industry.Scientific and rational production scheduling can more effectively improve resource utilization,reduce costs,reduce production time,and improve output and quality.Therefore,in the new situation,targeted production scheduling research for different issues is very necessaryThis article is based on the chip process needs to expose the wafer through a particular photomask with different integrated circuit diagrams on special parallel devices.Due to the limitations of photomasks,managers need to optimize the order of wafer processing,increase machine utilization,and maximize resource usage.Since the two parallel machines are the basic research model of the complex system,this paper proposes a two-station parallel machines scheduling problem with the goal of minimizing the maximum completion time under the mold limitationBased on the research of P2|fi|Cmax,this paper proposes heuristic algorithms and a branch and bound algorithm based on problem characteristics.The branch and bound algorithm can accurately find the best solution to the problem,and the solution to the problem is limited in scale;The heuristic algorithm is not limited by the size of the problem,and an approximate optimal solution can be obtained.The paper first establishes a mixed integer programming model and its lower bound model.The paper puts three heuristics of HLPT algorithm,LAPT algorithm and CHL algorithm on the LPT idea of balancing the machine load to reduce the machine's completion time According to the characteristics of the arrangement of the workpieces and the idea of branch and delimitation,the P-B&B algorithm is proposed.The paper makes a detailed demonstration and elaboration of the structure and process of the algorithms.It is proved that the worst case of the approximate optimal solution obtained by the proposed three HLPT algorithm,LAPT algorithm and CHL algorithm is ?=4/3.This is better than Chung(2019)TLPT algorithm,DMLPT algorithm and CTD algorithm.The three heuristic algorithms have the worst upper bound ratio ?=3/2.Proving the correctness of the lower bound 1 and lower bound 2 of the P-B&B algorithm,the optimality of no idle ordering and several subsectionsThis paper also implements algorithmic computer simulation experiments through C++ programming to evaluate and verify the quality of the algorithm.The scale of the problem solved by the algorithm is different,300 experimental problems are generated to the number of small-scale workpieces,and 320 experimental problems as the number of large-scale workpieces.Heuristic algorithms are evaluated by data experiments of different scales,such as percentage deviation of target values,number of optimal conditions,and running time.The results show that the CHL algorithm is the optimum algorithm for solving the best quality in the six algorithms in different data scale experiments.Secondly,the LAPT algorithm is better than the best CTD algorithm in the comparison group,especially in large-scale data experiments;The quality of the HLPT algorithm is between the TLPT algorithm and the DMLPT algorithm.In addition,the branch and bound method can only solve the small-scale problem,and thus compare the solving ability by the number of workpieces obtained by the AMPL software calling CPLEX to solve the mathematical model of the problem.The number of workpieces solved by P-B&B algorithm is 30%,so the quality is better.