主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
魏麒,蒋义伟.一类两阶段杂交流水作业的近似算法.软件学报,2012,23(5):1073-1084
一类两阶段杂交流水作业的近似算法
Approximation Algorithms for a Two-Stage Hybrid Flow Shop
投稿时间:2008-12-10  修订日期:2010-06-29
DOI:10.3724/SP.J.1001.2012.00587
中文关键词:  流水作业  计算复杂性  近似算法  最坏情况界  最后完工工件完工时间
英文关键词:flowshop scheduling  computational complexity  approximation algorithm  worst-case ratio  makespan
基金项目:国家自然科学基金(11001242, 11071220); 浙江省自然科学基金(Y6090554, Y6090175)
作者单位E-mail
魏麒 浙江大学 宁波理工学院, 浙江 宁波 315100  
蒋义伟 浙江理工大学 理学院, 浙江 杭州 310018 mathjyw@yahoo.com.cn 
摘要点击次数: 2321
全文下载次数: 2545
中文摘要:
      讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务:第1 个任务可以在任何一台机器上加工,第2 个任务只能在第1 个任务完成后在第2 台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2 个任务可以在第1 个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS 模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5 的多项式时间近似算法.对于NSHFS 模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3 的多项式时间近似算法.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利