|
|||||
|
|
Minimizing makespan on a single batching machine with release times and non-identical job sizes |
|
| Authors: | Shuguang Li Guojun Li Xiaoli Wang |
| Institution: | a Department of Mathematics and Information Science, Yantai University, Yantai 264005, People's Republic of China b School of Mathematics and System Science, Shandong University, Jinan 250100, People's Republic of China c Institute of Software, Chinese Academy of Sciences, Beijing 100080, People's Republic of China d School of Computer Science and Technology, Yantai Normal University, Yantai 264025, People's Republic of China |
| Abstract: | We consider the problem of scheduling jobs with release times and non-identical job sizes on a single batching machine; our objective is to minimize makespan. We present an approximation algorithm with worst-case ratio 2+ε, where ε>0 can be made arbitrarily small. |
| Keywords: | Approximation algorithms Scheduling Batch processing Makespan Release times |
| 本文献已被 ScienceDirect 等数据库收录！ | |