| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10348202 | Computers & Operations Research | 2012 | 10 Pages |
Abstract
⺠We study a two-machine flow-shop scheduling problem with rejection. ⺠We measure the quality of a schedule by two criteria: the makespan and the total rejection cost. ⺠We show that the problem of minimizing the sum of the two criteria (problem P1) is ordinary NP-hard. ⺠We provide an FPTAS and two 2-approximation algorithms for solving the P1 problem. ⺠The bicriteria problem is shown to be ordinary NP-hard and a two-dimensional FPTAS is provided.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Dvir Shabtay, Nufar Gasper,