...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computers & Industrial Engineering >Algorithms for scheduling incompatible job families on single batching machine with limited capacity
【24h】

Algorithms for scheduling incompatible job families on single batching machine with limited capacity

机译：在容量有限的单个配料机上调度不兼容的作业族的算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Motivated by applications in food processing and semiconductor manufacturing industries, we consider the scheduling problem of a batching machine with jobs of multiple families. The machine has a limited capacity to accommodate jobs. The jobs are in arbitrary sizes and multiple families. Jobs from different families cannot be processed in a batch. We show the problems of minimizing makespan and total batch completion time are both NP-hard in the strong sense. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the special case where a larger job also has a longer processing time, the heuristic for minimizing makespan is optimal. For the general case, we show the performance guarantee of the methods for the two objectives respectively.
机译：受食品加工和半导体制造行业应用的启发，我们考虑了具有多个家庭工作的配料机的调度问题。机器容纳工作的能力有限。这些作业具有任意大小和多个家庭。来自不同家庭的作业无法批量处理。我们从强烈的意义上证明了最小化制造时间和总批次完成时间的问题都是NP难的。我们针对这些问题提出了一个混合整数规划模型。然后根据最长处理时间的第一规则和第一拟合规则，提出了两种多项式时间启发式算法。对于较大的工作也有较长的处理时间的特殊情况，最小化制造期的启发法是最佳的。对于一般情况，我们分别显示了针对两个目标的方法的性能保证。

著录项

  • 来源
    《Computers & Industrial Engineering》 |2014年第9期|116-120|共5页
  • 作者

    Bayi Cheng; Junfeng Cai; Shanlin Yang; Xiaoxuan Hu;

  • 作者单位

    School of Management, Hefei University of Technology, Hefei 230009, PR China Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei University of Technology, Hefei 230009, PR China;

    School of Management, Hefei University of Technology, Hefei 230009, PR China Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei University of Technology, Hefei 230009, PR China;

    School of Management, Hefei University of Technology, Hefei 230009, PR China Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei University of Technology, Hefei 230009, PR China;

    School of Management, Hefei University of Technology, Hefei 230009, PR China Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei University of Technology, Hefei 230009, PR China;

  • 收录信息
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Scheduling; Single batching machine; Incompatible job families; Arbitrary job sizes; Approximation algorithm;

    机译：排程;单配料机;不兼容的工作家庭;任意工作规模;近似算法;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号