文献类型：期刊文献

英文题名：A best possible on-line algorithm for two-machine flow shop scheduling to minimize makespan

作者：Liu, Peihai[1];Lu, Xiwen[1]

机构：[1]E China Univ Sci & Technol, Sch Sci, Dept Math, Shanghai 200237, Peoples R China

年份：2014

卷号：51

起止页码：251

外文期刊名：COMPUTERS & OPERATIONS RESEARCH

收录：;EI(收录号：20142917943324);WOS:【SCI-EXPANDED(收录号:WOS:000341473200023)】；

基金：This work was supported by the National Nature Science Foundation of China (11101147 and 11371137) and the Fundamental Research Funds for the Central Universities.

语种：英文

外文关键词：Scheduling Flow shop; Online; Competitive; ratio

摘要：We address a two-machine flow shop on-line scheduling problem. Jobs arrive over time. Each job becomes available for processing at its release time after which it must be processed without preemption on the first machine and then on the second machine. The objective is to minimize the makespan. We provide a best possible deterministic on-line algorithm with a competitive ratio of (root 5+1)/2. Computational experiments on randomly generated problem instances are performed and the results show that the online algorithm is very useful to obtain near-optimal solutions. (C) 2014 Elsevier Ltd. All rights reserved.