Premium
Two‐machine flowshop scheduling with conditional deteriorating second operations
Author(s) -
Lin B. M. T.,
Cheng T. C. E.
Publication year - 2006
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2006.00536.x
Subject(s) - job shop scheduling , computer science , scheduling (production processes) , flow shop scheduling , mathematical optimization , job shop , mathematics , schedule , operating system
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 ‐hard. We then develop an O ( n 2 ) algorithm to determine the makespan of a processing sequence of the jobs.