Quick dispatching-rules-based solution for the two parallel machines problem under mold constraints

The main focus of this study is on the makespan minimization scheduling problem on two identical parallel machines with mold constraints. The mold constraint in this problem is described as a resource-constrained problem. In industries such as wafer fabrication, two tasks that use the same mold cannot be processed simultaneously on two parallel machines. Because the problem is NP-hard, ten heuristics have been developed and discussed to describe and solve the problem. These heuristics are based on the dispatching rules, the critical mold approach, the clustering method, and the probabilistic method using the randomization procedure. In addition, a new lower bound is proposed. Four classes with a total of 2160 instances are generated to assess the performance of the proposed algorithms. The computational results showed that the proposed lower bound and heuristics outperform those developed in the literature. In addition, the obtained results showed that the optimal solution is reached in 97.6% of the generated instances.

Automated summary

The main focus of this study is the scheduling problem of minimizing the makespan on two identical parallel machines with mold constraints. The mold constraint is described as a resource-constrained problem. Ten heuristics based on different approaches have been developed and discussed to solve the NP-hard problem. In addition, a new lower bound is proposed and computational results show the effectiveness of the heuristics and the higher performance of the proposed lower bound.