Study On Parallel Machines With Mold Constraint Scheduling Problem

In the fourth industrial revolution background, scheduling problems in the workshop of intelligent manufacturer are received more and more attention by the manufacturer. Especially in the high technique and automatic production line, the optimization of production process is very important for increasing production efficient, keeping costs down and ensuring the output. With the improvement of the mode of production, the constraints in scheduling problem are keeping closer to real world and the study of these problems provides many reliable bases and references on production scheduling problem.This paper deals with makespan minimization scheduling problem on identical parallel machines with a mold constraint. In semiconductor plant, exposing of the wafer should be with a specific mold in the parallel machines. Each wafer has a specific mold and the number of wafer is limited. To increase the efficiency of this stage and optimize the process of production, the order for wafer production should be decided to fulfill the object, minimizing the makespan.A bank of machines in parallel is a setting that is important from both a theoretical and a practical point of view. From a theoretical point of view, it is a generalization of the single machine, and a special case of the flexible flow shop. From a practical point of view, it is important because the occurrence of resources in parallel is common in the real world. Also, techniques for machines in parallel are often used in decomposition procedures for multi-stage systems. Minimizing makespan on identical parallel machine can be denoted as maxP|| C. Even if on the two identical parallel machines without mold constraint is known to be NP-hard problem. First, a mathematical model including the jobs position constraint and mold constraint is discussed to describe and solve the problem. Besides, the optimal solution of the max||mP C problem which is a slack problem of max| |iP m C is used as a lower bound. Next, two conditions are provided according to the characteristic of the problem and two heuristics are proposed to solve the max| |iP m C problem with large job number efficiently. For both proposed heuristics, the worst case performance ratios were all derived by 3/2. Time requirement for the heuristic algorithms are proposed to make a contrastive analysis. Finally, these two modified algorithms, named DMLPT/TLPT-VNS and DMLPT/TLPT-DPSO, are used to evaluate two proposed heuristics by the improvement of solutions. One hand, the particle and the velocity are redefined in the DPSO algorithm. On the other hand, DMLPT and TLPT, are also applied to be initial solutions for the VNS.Computational results show that two proposed heuristics and the modified algorithms can efficiently yield a near optimal solution. Especially in the extensive experiments for DMLPT and TLPT comparison analysis, the proposed heuristics can efficiently yield better solutions and DMLPT perform better as job number is increasing.