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

作者简介:

通讯作者:

基金项目:

国家自然科学基金面上项目(No.71371120);教育部人文社会科学研究青年基金项目(No.23YJC790046)


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

Fund Project:

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

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

    Abstract:

    Flow shop scheduling where each job can be either processed in-house shop or outsourced to a subcontractor is studied. The jobs in-house are processed in serial batches, i.e., the jobs are processed in batches on the machine in a serial manner and the processing time of a batch is the sum of the processing times of all jobs in the batch. And all the jobs are shipped to customers in batches after processing. Each of the outsourced jobs requires paying an outsourcing cost. 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. Two special cases where job’s processing time depends solely on job itself or on the machine 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.

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

陈荣军,唐国春.转包费用有限的串行分批加工流水作业排序问题[J].重庆师范大学学报自然科学版,2025,42(3):17-23

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2025-07-16