Heuristics for assembly operation scheduling problem in flexible assembly systems

In this paper we address the problem of scheduling n assembly operations with in-tree constraints on m unrelated parallel workstations in flexible assembly systems, which we call the assembly operation scheduling problem (AOSP). No preemption of assembly operations is allowed and the primary objective is to minimize the maximum completion time. This problem is equivalent to R|tree|C_max. For this notorious NP-hard problem, four heuristic algorithms including decomposition (DECOMP), earliest completion time (ECT), shortest processing time (SPT), and earliest starting time(EST) heuristic are proposed and their performances are comparatively investigated. DECOMP uses a decomposition technique to practically solve this problem. The assembly operation tree is decomposed and then AOSP is reduced to a set of subproblems of R||C_max and R,r_j|r_i|C_max. Two efficient heuristics were proposed for the reduced subproblems. The other three heuristics basically use the machine selection rules to determine the machine for processing the current operation. Of these heuristics, DECOMP showed the best performance in terms of quality of schedule. Computational results show that all the proposed algorithms except the EST heuristic perform quite well in terms of both quality of solution and computation time.