|
|||||
|
|
Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs |
|
| Authors: | Cuixia Miao Yuzhong Zhang |
| Affiliation: | a School of Mathematical Sciences, Qufu Normal University, Qufu, Shandong 273165, People?s Republic of China b School of Management, Qufu Normal University, Rizhao, Shandong 276826, People?s Republic of China c Key Laboratory of Management Decision and Information Systems AMSS, CAS, Beijing 100190, People?s Republic of China |
| Abstract: | We consider the bounded parallel-batch scheduling problem in which the processing time of a job is a simple linear function of its starting time. The objective is to minimize the makespan. When the jobs have identical release dates, we present an optimal algorithm for the single-machine problem and an fully polynomial-time approximation scheme for the parallel-machine problem. When the jobs have distinct release dates, we show that the single-machine problem is NP-hard and present an optimal algorithm for one special case. |
| Keywords: | Analysis of algorithms Parallel-batch scheduling Deteriorating job NP-hard Fully polynomial time approximation scheme (FPTAS) |
| 本文献已被 ScienceDirect 等数据库收录！ | |