Two-machine open-shop scheduling with rejection to minimize the makespan |
| |
Authors: | Liqi Zhang Lingfa Lu Jinjiang Yuan |
| |
Affiliation: | 1.College of Information and Management Science,Henan Agricultural University,Zhengzhou,People’s Republic of China;2.School of Mathematics and Statistics,Zhengzhou University,Zhengzhou,People’s Republic of China |
| |
Abstract: | In this paper, we consider the two-machine open-shop scheduling problem with rejection. The objective is to minimize the sum of the makespan of accepted jobs and the total rejection cost of rejected jobs. We show that the problem is NP-hard even in three special cases and then provide a pseudo-polynomial time algorithm for this problem, which means that the problem is actually NP-hard in the ordinary sense. This answers an open problem posed by Shabtay et al. in (J Schedul 16:3–28, 2013). Finally, a 2-approximation algorithm and an FPTAS are designed for the problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|