Parallel-machine scheduling with simple linear deterioration to minimize total completion time |
| |
Authors: | Min Ji TCE Cheng |
| |
Institution: | 1. College of Computer Science and Information Engineering, Zhejiang Gongshang University, Hangzhou 310018, PR China;2. Department of Logistics, The Hong Kong Polytechnic University, Kowloon, Hong Kong |
| |
Abstract: | We consider the parallel-machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time. The objective is to minimize the total completion time. We give a fully polynomial-time approximation scheme (FPTAS) for the case with m identical machines, where m is fixed. This study solves an open problem that has been posed in the literature for ten years. |
| |
Keywords: | Parallel-machine scheduling Deteriorating jobs FPTAS |
本文献已被 ScienceDirect 等数据库收录! |
|