转包费用有限的串行分批加工流水作业排序问题
DOI:
作者:
作者单位:

1.常州工学院;2.上海第二工业大学

作者简介:

通讯作者:

基金项目:

国家自然科学基金项目(71371120)和教育部人文社科项目(23YJC790046)资助


Serial Batch Flow Shop Scheduling with Limited Outsourcing Costs
Author:
Affiliation:

1.Changzhou Institute of Technology;2.Shanghai Second Polytechnic University

Fund Project:

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

    【目的】研究工件既可以在制造商机器上加工、又可以转包给承包商加工的m台机流水作业排序问题。【方法】考虑工件在制造商机器上以串行分批方式加工,且加工后被分批运送给客户;同时,因部分工件被转包给承包商加工,还考虑制造商需要支付一定的转包费用。【结果】在转包总费用不超过给定值情况下,研究极小化工件加工成本与运输成本之和的有效算法,其中,加工成本分别取制造商处工件最大完工时间及工件总完工时间,运输成本则与工件批数成正比。【结论】对于工件加工时间仅与工件特征值有关的情形,针对不同的加工成本,分析了问题的NP困难性及最优解的结构,分别设计了两个近似算法;对于工件加工时间仅与机器特征值有关的情形,则在分析解结构的基础上提出了两个多项式时间算法。

    Abstract:

    [Purposes]Flow shop scheduling where each job can be either processed in-house shop or outsourced to a subcontractor is studied in this paper. [Methods]The jobs in-house are processed in serial batches and are delivered to customers in batches after processing. Each of the outsourced jobs requires paying an outsourcing cost. [Findings]The objective is to minimize the sum of the performance measure (the total completion time or the makespan) and transportation cost for in-house jobs, subject to a limit on total outsourcing cost. The transportation cost is proportional to the batch number of jobs. [Conclusions]Two special cases where job's processing time is determined only by job parameters or by machine parameters are considered. In the first case, two approximation algorithms are designed respectively for different performance measures after the NP hardness of the problem and the structure of the optimal solution are analyzed. On the basis of analyzing the solution structure, two polynomial algorithms are proposed in the second case.

    参考文献
    相似文献
    引证文献
引用本文
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:2024-04-12
  • 最后修改日期:2025-01-19
  • 录用日期:2025-04-15
  • 在线发布日期: