Fabrication and assembly scheduling in a two-machine flowshop

Research output: Journal article publicationJournal articleAcademic researchpeer-review

26 Citations (Scopus)

Abstract

This paper considers a fabrication scheduling problem to minimize the makespan in a two-machine flowshop. Each job has a unique component and a common component to be processed on the first machine. On machine 1, the common components of the jobs are grouped into batches for processing with a setup cost incurred whenever a batch is formed. A job is ready for its assembly operation on the second machine if both its unique and common components are finished on machine 1. The problems with batch availability and item availability are known as NP-hard. In this paper, we give proofs for the strong NP-hardness of the two problems. The results suggest that it is very unlikely to develop polynomial- or pseudo-polynomial-time algorithm for finding exact solutions for the two problems.
Original languageEnglish
Pages (from-to)1015-1020
Number of pages6
JournalIIE Transactions (Institute of Industrial Engineers)
Volume34
Issue number11
DOIs
Publication statusPublished - 1 Nov 2002

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering
  • Management Science and Operations Research

Cite this