A two-stage three-machine assembly scheduling problem with a truncation position-based learning effect

The two-stage assembly scheduling problem has a lot of applications in industrial and service sectors. Furthermore, truncation-based learning effects have received growing attention in connection with scheduling problems. However, it is relatively unexplored in the two-stage assembly scheduling problem. Therefore, we addressed the two-stage assembly with truncation learning effects with two machines in the first stage and an assembly machine in the second stage. The objective function was to complete all jobs as soon as possible (or to minimize the makespan). Due to the NP-hardness of the considered problem, we proposed several dominance relations and a lower bound for the branch-and-bound method for finding the optimal solution. Moreover, we proposed six versions of hybrids greedy iterative algorithm, where three versions of the local searches algorithm with and without a probability scheme are embedded. They include extraction and backward-shifted reinsertion, pairwise interchange and extraction and forward-shifted reinsertion for searching good-quality solutions. The experimental results of all proposed algorithms are presented on small-size and big-size jobs.