Name
Abstract | ||
|---|---|---|
A two-machine flow shop scheduling problem with rejection is considered in this paper. The objective is to minimize the sum of makespan of accepted operations and total penalty of rejected operations. Each job has two operations that could be rejected, respectively. Operations on the first machine have penalties alpha 1 times of their processing times and operations on the second machine have penalties alpha 2 times of their processing times. A 4/3-approximation algorithm is presented for the case where min{alpha 1, alpha 2} < 1 and max {alpha 1, alpha 2} >= 1. A dynamic programming algorithm is provided for general a1 and alpha 2. A fully polynomial-time approximation scheme (FPTAS) is designed for all NP-hard cases. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1142/S021759591450002X | ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH |
Keywords | Field | DocType |
Flow shop scheduling,rejection,operation's penalty,FPTAS | Mathematical optimization,Job shop scheduling,Computer science,Flow shop scheduling,Real-time computing | Journal |
Volume | Issue | ISSN |
31 | 1 | 0217-5959 |
Citations | PageRank | References |
1 | 0.35 | 11 |
Authors | ||
2 | ||