Two-machine flowshop scheduling with conditional deteriorating second operations

B. M.T. Lin, T. C.E. Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)

Abstract

This paper considers a flowshop-scheduling problem with a waiting time constraint imposed to restrict the processing of the two operations of each job. If the second operation of a job cannot start within a specified waiting time after the completion of its first operation, then an extra processing time will be incurred for its second operation as a penalty. We first show that even a greatly restricted version of the problem is strongly N P-hard. We then develop an O(n2) algorithm to determine the makespan of a processing sequence of the jobs.
Original languageEnglish
Pages (from-to)91-98
Number of pages8
JournalInternational Transactions in Operational Research
Volume13
Issue number2
DOIs
Publication statusPublished - 1 Jan 2006

Keywords

  • Flowshop scheduling
  • Makespan
  • N P-hardness
  • Waiting time

ASJC Scopus subject areas

  • Business and International Management
  • Computer Science Applications
  • Strategy and Management
  • Management Science and Operations Research
  • Management of Technology and Innovation

Cite this