单机带有不可用区间的松弛工期的排序问题
作者:
作者单位:

作者简介:

通讯作者:

基金项目:

国家自然科学基金——重大项目(No.11991022),面上项目(No.11971443);重庆市教育委员会科学技术研究计划重点项目(No.KJZD-K202000501);重庆市自然科学基金面上项目 (No.cstc2021jcyj-msxmX0229)


Single-Machine Scheduling Problem with Unavailability Period for Slack Due Date
Author:
Affiliation:

Fund Project:

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

    研究了在单机情形下具有不可用区间的松弛工期问题,不可用区间意味着在此区间不允许工件加工,且工件中断可恢复。松弛工期是工件加工时间加上1个给定的常数,这个常数为决策变量,排序的任务是给所有工件分配工期,同时确定工件的加工次序以使得目标函数值最小。目标函数值包括由于工件误工、提前及工期分配而导致的相关损失。根据不同的损失系数关系讨论了松弛工期的范围,提出动态规划算法。证明了动态规划的时间复杂性为O((P+T-pmin)nP2)。通过算例分析说明了算法的可行性。

    Abstract:

    The single-machine problem with unavailability period for slack due date is studied. Unavailability period means that the processing job is not allowed in this period. Slack due date means that the due date is equal to its processing time plus a constant, where the constant is the decision variable. The aim is to assign the slack due and minimize the objective function. The objective function includes the early work, late work and slack due date. It discusses the range of slack due date by cost coefficients, and designs a dynamic programming algorithm to solve this problem. It is prove that the optimal solution can be obtained in O((P+T-Pmin)nP2) time. Finally, a numerical example is presented to illustrate the feasibility of the algorithms.

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

唐小敏,张新功.单机带有不可用区间的松弛工期的排序问题[J].重庆师范大学学报自然科学版,2024,41(2):37-41

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