Semi-online scheduling on two identical machines with rejection |
| |
Authors: | Xiao Min Yuqing Wang Jing Liu Min Jiang |
| |
Institution: | 1. College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing, Zhejiang, 314001, China 2. Xianda College of Economics and Humanities, Shanghai International Studies University, Shanghai, 200083, China 3. Computer School, Hangzhou Dianzi University, Hangzhou, 310018, China
|
| |
Abstract: | In this paper we consider two semi-online scheduling problems with rejection on two identical machines. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. In the first problem one can reassign several scheduled jobs in rejection tache, in the second a buffer with length k is available in rejection tache. Two optimal algorithms both with competitive ratio $\frac{3}{2}$ are presented. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|