A comparison of hybrid genetic algorithm and hybrid particle swarm optimization to minimize makespan for assembly job shop

T.C. Wong, S.C. Ngan

Research output: Contribution to journalArticlepeer-review

54 Citations (Scopus)


Very often, studies of job shop scheduling problem (JSSP) ignore assembly relationship and lot splitting. If an assembly stage is appended to JSSP for the final product, the problem then becomes assembly job shop scheduling problem (AJSSP). To allow lot splitting, lot streaming (LS) technique is examined in which jobs may be split into a number of smaller sub-jobs for parallel processing on different stages such that the system performance may be improved. In this study, the system objective is defined as the makespan minimization. In order to investigate the impact of LS on the system objective under different real-life operating conditions, part sharing ratio (PSR) and system congestion index (SCI) are considered. PSR is used to differentiate product-specific components from general-purpose, common components, and SCI for creating different starting conditions of the shop floor. Both PSR and CSI are useful as part sharing (also known as component commonality) is a common practice for manufacturing with assembly operations and system loading is a significant factor in influencing the shop floor performance. Since the complexity of AJSSP is NP-hard, a hybrid genetic algorithm (HGA) and a hybrid particle swarm optimization (HPSO) are proposed and developed to solve AJSSP in consideration of LS technique. Computational results show that for all test problems under various system conditions, HGA can significantly outperform HPSO. Also, equal-sized lot splitting is found to be the most beneficial LS strategy especially for medium-to-large problem size.
Original languageEnglish
Pages (from-to)1391-1399
Number of pages9
JournalApplied Soft Computing
Issue number3
Publication statusPublished - 1 Jan 2013


  • hybrid genetic algorithm
  • hybrid particle
  • swarm optimization
  • makespan
  • assembly job shop

Cite this