An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem

被引：11

作者：

Elalouf, Amir ^{[1
]}

Levner, Eugene ^{[2
]}

Tang, Huajun ^{[3
]}

机构：

[1] Bar Ilan Univ, Ramat Gan, Israel

[2] Ashkelon Acad Coll, Ashqelon, Israel

[3] Macau Univ Sci & Technol, Macao, Peoples R China

来源：

JOURNAL OF SCHEDULING | 2013年 / 16卷 / 04期

关键词：

Just-in-time scheduling; Flow shop; Complexity; Pseudo-polynomial algorithm; FPTAS; RESTRICTED SHORTEST-PATH;

D O I：

10.1007/s10951-013-0320-6

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

Recently, Shabtay and Bensoussan (2012) developed an original exact pseudo-polynomial algorithm and an efficient -approximation algorithm (FPTAS) for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. The complexity of the FPTAS is (()log(/)), where is the number of jobs. In this note we suggest another pseudo-polynomial algorithm that can be converted to a new FPTAS which improves Shabtay-Bensoussan's complexity result and runs in time.

引用

页码：429 / 435

页数：7

共 10 条

[1] Maximizing the weighted number of just-in-time jobs in flow shop scheduling
Choi, Byung-Cheon
Yoon, Suk-Hun
[J]. JOURNAL OF SCHEDULING, 2007, 10 (4-5) : 237 - 243
[2] Elalouf A, 2011, LECT NOTES BUS INF P, V88, P1
[3] An improved FPTAS for Restricted Shortest Path
Ergun, F
Sinha, R
Zhang, L
[J]. INFORMATION PROCESSING LETTERS, 2002, 83 (05) : 287 - 291
[4] FAST APPROXIMATION ALGORITHM FOR JOB SEQUENCING WITH DEADLINES
GENS, GV
LEVNER, EV
[J]. DISCRETE APPLIED MATHEMATICS, 1981, 3 (04) : 313 - 318
[5] Graham R. L., 1979, Discrete Optimisation, P287
[6] APPROXIMATION SCHEMES FOR THE RESTRICTED SHORTEST-PATH PROBLEM
HASSIN, R
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1992, 17 (01) : 36 - 42
[7] Lann A., 1996, COMPUTERS OPERATIONS, V23, P765
[8] Levner E, 2011, J UNIVERS COMPUT SCI, V17, P1854
[9] A simple efficient approximation scheme for the restricted shortest path problem
Lorenz, DH
Raz, D
[J]. OPERATIONS RESEARCH LETTERS, 2001, 28 (05) : 213 - 219
[10] Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems
Shabtay, Dvir
Bensoussan, Yaron
[J]. JOURNAL OF SCHEDULING, 2012, 15 (01) : 39 - 47

← 1 →