Two-machine flowshop scheduling with conditional deteriorating second operations

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

doi:10.1111/j.1475-3995.2006.00536.x

Two-machine flowshop scheduling with conditional deteriorating second operations

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

The Hong Kong Polytechnic University

Research output: Journal article publication › Journal article › Academic research › peer-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 language	English
Pages (from-to)	91-98
Number of pages	8
Journal	International Transactions in Operational Research
Volume	13
Issue number	2
DOIs	https://doi.org/10.1111/j.1475-3995.2006.00536.x
Publication status	Published - 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

More information

10.1111/j.1475-3995.2006.00536.x

http://hdl.handle.net/10397/645

Cite this

@article{ab923eaf07b64ffd94215fd65737a1c7,

title = "Two-machine flowshop scheduling with conditional deteriorating second operations",

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.",

keywords = "Flowshop scheduling, Makespan, N P-hardness, Waiting time",

author = "Lin, {B. M.T.} and Cheng, {T. C.E.}",

year = "2006",

month = jan,

day = "1",

doi = "10.1111/j.1475-3995.2006.00536.x",

language = "English",

volume = "13",

pages = "91--98",

journal = "International Transactions in Operational Research",

issn = "0969-6016",

publisher = "John Wiley and Sons Inc",

number = "2",

}

TY - JOUR

T1 - Two-machine flowshop scheduling with conditional deteriorating second operations

AU - Lin, B. M.T.

AU - Cheng, T. C.E.

PY - 2006/1/1

Y1 - 2006/1/1

N2 - 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.

AB - 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.

KW - Flowshop scheduling

KW - Makespan

KW - N P-hardness

KW - Waiting time

UR - http://www.scopus.com/inward/record.url?scp=85007084598&partnerID=8YFLogxK

U2 - 10.1111/j.1475-3995.2006.00536.x

DO - 10.1111/j.1475-3995.2006.00536.x

M3 - Journal article

SN - 0969-6016

VL - 13

SP - 91

EP - 98

JO - International Transactions in Operational Research

JF - International Transactions in Operational Research

IS - 2

ER -

Two-machine flowshop scheduling with conditional deteriorating second operations

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this