Minimizing make-span in 2-stage disassembly flow-shop scheduling problem

• Addressed the 2 stage m-machine disassembly flow-shop (2SmMDF) scheduling problem.
• Showed that 2S2MDF is NP-complete.
• Suggested three heuristics based on Johnson’s rule and showed their worst case performance.

In this paper we address the 2-stage m-machine (in Stage 2) disassembly flow-shop (2SmMDF) scheduling problem. It consists of n   jobs, each requiring m+1m+1 tasks. The first task is the disassembly of a job, and it leads to m processing tasks each of which is performed on a different machine. The objective is to minimize the make-span. First we show that 2SmMDF problem for the make-span criterion is NP-complete. Then we propose the following three heuristic methods for its solution: H1: determine the maximum of Stage 2 task times for each job and use that and the time required for the first task to schedule the jobs according to the Johnson’s rule; H2: determine the total time required at each Stage 2 machine over all the jobs and use the time of the machine with the largest total time and the time required for the first task to schedule the jobs according to the Johnson’s rule; H3: determine the average of Stage 2 times for each job and use that and the time required for the first task to schedule the jobs according to the Johnson’s rule. Finally, we present the worst-case performance analysis for each method, and show that method H3 has a slightly better worst-case performance bound.