科研之友
微信
新浪微博
Facebook
分享链接
摘要
In this paper, we consider the scheduling problem in which the processing time of a job is a linear increasing function of its starting time and machine with availability constraints. The objective is to minimize the makespan. We first present a fully polynomial-time approximation scheme (FPTAS) for the case with a single machine. We then show that there exists no polynomial time approximation algorithm with a constant worst-case bound for the case with two identical machines unless P = NP.
- 出版日期2016-12
- 单位沈阳师范大学
