An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times |
| |
Authors: | Ming Liu Chengbin Chu Yinfeng Xu Feifeng Zheng |
| |
Affiliation: | 1. School of Management, Xi’an Jiaotong University, 710049, Xi’an, Shaanxi, People’s Republic of China 2. Laboratoire Génie Industriel, Ecole Centrale Paris, Grande Voie des Vignes, 92295, Chatenay-Malabry Cedex, France 3. State Key Laboratory for Manufacturing Systems Engineering, 710049, Xi’an, Shaanxi, People’s Republic of China
|
| |
Abstract: | This paper deals with a two-machine open shop scheduling problem. The objective is to minimize the makespan. Jobs arrive over time. We study preemption-resume model, i.e., the currently processed job may be preempted at any moment in necessary and be resumed some time later. Let p 1, j and p 2, j denote the processing time of a job J j on the two machines M 1 and M 2, respectively. Bounded processing times mean that 1 ≤ p i, j ≤ α (i = 1, 2) for each job J j , where α ≥ 1 is a constant number. We propose an optimal online algorithm with a competitive ratio ${frac{5alpha-1}{4alpha}}$ . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|