固定区间下的可中断单机双代理总加权误工问题
作者:
作者单位:

作者简介:

通讯作者:

基金项目:

国家自然科学基金重大项目(No.11991022);国家自然科学基金面上项(No.11971443);重庆市教育委员会重点项目(No.KJZD-K202000501);重庆市科学技术局项目(No.cstc2021jcyj-msxmX0229);最优化理论与方法及其应用创新创业示范团队项目(No.CQYC20210309536);川西南空间效应探测与应用四川省高等学校重点实验室基金(No.YBXM202201001)


Total Weighted Tardiness with Preempted Jobs and Fixed Time Windows on a Single Two-Agent Machine
Author:
Affiliation:

Fund Project:

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

    【目的】研究在固定区间内工件可中断的单机双代理排序问题。【方法】每个代理都有各自对应的工件集合以及目标函数,它们只能共同使用1台机器来完成各自工件的加工,每个代理的目标都是最小化各自的目标函数。第一个代理工件可中断且到达时间与工期满足一致性关系,目标函数为总加权误工费用;第二个代理中工件位于固定时间窗口内进行加工。【结果】排序的目的是为了第二个代理中工件满足加工时间区间等于固定区间条件下,使得第一个代理的目标函数达到最小化。【结论】利用了分块的原则,给出了最优性质刻画和复杂性分析,以及设计了一个伪多项式时间动态规划算法。

    Abstract:

    [Purposes]Total weighted tardiness problems can be computed by the completion time of jobs after their due date. [Methods]It studies two-agent scheduling problems with fixed time windows on a single machine, the objective function is to minimize the total weighted tardiness of the first agent. Two agent scheduling problem means that each agent has its job set, in which it can be processed in the common machine, and is used to minimize the its objective function. Assume that jobs of the first agent is preempted, there exists an agreeable condition for due date and release date. [Findings]The jobs of the second agent are processed in some fixed due date window. [Conclusions]By the block principle, the time complexity of the proposed problem is put forward and a pseudo-polynomial time dynamic programming algorithm is presented when a fixed time window equals the processing time.

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

李中华,唐小敏,赵文平,张新功.固定区间下的可中断单机双代理总加权误工问题[J].重庆师范大学学报自然科学版,2023,(1):15-20

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