Heuristics for assembly operation scheduling problem in flexible assembly systems

Bongju Jeong, Seung Bae Sim, Hosang Jung

Research output: Contribution to journalArticlepeer-review


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|Cmax. 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||Cmax and R,rj|ri|Cmax. 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.

Original languageEnglish
Pages (from-to)1033-1040
Number of pages8
JournalInternational Journal of Advanced Manufacturing Technology
Issue number9-10
Publication statusPublished - 2006 Jul

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Mechanical Engineering
  • Computer Science Applications
  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Heuristics for assembly operation scheduling problem in flexible assembly systems'. Together they form a unique fingerprint.

Cite this