Approximation Algorithms for a Two-Stage Hybrid Flow Shop
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    This paper investigates a variant scheduling problem of minimizing makespan in a two-machine flow shop. In this variant, there will be two tasks for each job. The first task can be processed on either machine, and the second task can only be processed on the second machine after the first task has been finished. Furthermore, if the second task should start right after the first task is completed, it is called a no-waited case and is denoted by NSHFS. On the other hand, if the second task is allowed to be processed at any time after the first task is completed, the problem is then denoted as SHFS. In the case of SHFS, based on the result of Wei and He, an improved polynomial time approximation algorithm with worst-case ratio of 8/5 is presented. In the case of NSHFS, this paper shows that it is NP-hard, and presents a polynomial time approximation algorithm with worst-case ratio of 5/3.

    Reference
    Related
    Cited by
Get Citation

魏麒,蒋义伟.一类两阶段杂交流水作业的近似算法.软件学报,2012,23(5):1073-1084

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:December 10,2008
  • Revised:June 29,2010
  • Adopted:
  • Online: April 29,2012
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063