欢迎访问《空军工程大学学报》官方网站!

咨询热线:029-84786242 RSS EMAIL-ALERT
可拆分平行机排序问题的一个启发式算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP301

基金项目:

国家自然科学基金资助项目(60574075)


A Heuristic Algorithm for Parallel Machine Scheduling Problem with Job Splitting Property
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    为缩短工件的完工时间,将极小化最大完工时间的平行机排序问题作为研究目标。在此问题中,允许同一工件拆分成多个子工件在不同的机器上同时加工,同一工件的任何2个子工件不可在同一台机器上加工。与以往研究不同,对工件的拆分方式进行了限制,即工件拆分后所得子工件的长度不能小于给定的阀值,且工件拆分次数尽量少,这是一个NP难问题。借助于LPT算法的思想,提出了一个求解该问题的启发式算法,实现了工件的自动拆分和工件到机器上的自动分配。通过多个实例对文中算法进行了测试,数值结果表明:该算法可行、稳定性良好,适用于工件拆分方式具有类似限制的平行机排序问题的方案决策。

    Abstract:

    An identical parallel machine scheduling problem with job splitting to minimize makespan is studied to decrease the completion time of the job. In this problem, each job can be split into sections, which can be processed in parallel on different machines. There is at most one part of each job on a machine. Different from researches in the scheduling literatures, there is a restriction for the split, i.e. the size of each split section cannot be smaller than a given value and the splitting actions should be kept as less as possible in the number of times. For this NP-hard problem, a heuristic algorithm is developed based on the LPT algorithm. Using the algorithm, job is split and assigned automatically. The performance of the algorithm is evaluated through a number of numerical instances. The results show that the algorithm is feasible and fine in stability. This algorithm can be applied to solving parallel machine scheduling problem,in which the split has the similar restriction.

    参考文献
    相似文献
    引证文献
引用本文

郑秋亚,刘三阳,杨尊袍.可拆分平行机排序问题的一个启发式算法[J].空军工程大学学报,2010,(4):84-88

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2015-11-17
  • 出版日期: