带有固定区间的单机双代理可中断总误工问题

作者：陈秋宏; 张新功^*

来源：运筹学学报, 2019, 23(01): 61-71.

DOI：10.15960/j.cnki.issn.1007-6093.2019.01.007

• 单台机器
• 两个代理
• 总误工
• 固定时间窗口

研究带有固定区间的两个代理单机排序问题.第一个代理工件可中断,且工件到达时间与工期满足一致关系,目标函数为最小化总误工.第二个代理工件被安排在固定时间窗口.目标是寻找一个排序,使得满足第二个代理目标可行情况下,第一个代理目标函数值最小.在固定区间等于加工时间的情况下,利用分块原则,提出了一个伪多项式时间动态规划算法,并给出了固定区间大于加工时间情况下的时间复杂度分析.

• 单位
  重庆师范大学