同时最优化时间表长与总完工时间的双代理单机序列分批排序问题

本文研究在一台序列分批处理机上同时最优化A代理的时间表长和B代理的总完工时间的双代理排序问题.在序列分批的背景下,工件被分批加工(但不同代理的工件不能在同一批中加工,且每个代理都希望最小化仅依赖于各自工件完工时间的费用函数)且一批的加工时间等于这一批中所有工件的加工时间和.而且在一个新批开始加工前,机器有一个常数的安装时间.此外,根据批容量,序列分批模型又被分成有界模型和无界模型.在本文中,我们对所研究问题的有界模型和无界模型分别给出了一个多项式时间算法.

具有一致性的双代理有界序列分批排序问题

本文考虑带有两个代理工件的同时最小化A代理的时间表长和B代理的最大延迟的有界序列分批排序问题。不同代理的工件不可在同一批中加工,且不同代理的费用函数只和自身代理的工件有关。当工件的加工时间和工期具有一致性时,我们给出了找到该问题所有Pareto最优点的一个多项式时间算法。

同时最小化最大费用和最大完工时间的双代理无界平行分批排序

有两个代理A和B,每个代理都各自有一个工件集.同一个代理的工件可以在同一批中加工,而且每一个代理都有一个需要最小化的函数.研究在无界平行分批处理机上同时最小化代理A的最大费用和代理B的最大完工时间问题,并给出一个算法,它可在多项式时间内找到关于这个问题的所有Pareto最优点.

最小化总完工时间且工件可拒绝的单机双代理多任务排序问题

研究了工件可拒绝的双代理单机多任务排序问题。所谓多任务环境即是指当某个工件(主工件)在加工时,会被其余未完成加工的工件(这里称为等待工件)所打扰。而双代理之间不可互相打扰,它们共同使用单台机器来完成各自工件的加工,第1个代理目标函数为最小化总完工时间,第2个代理最大完工时间不超过某个上界。给定总拒绝费用的允许上界,每个工件有2个选择:接受或拒绝。排序目的是为了第2个代理最大完工时间不超过某个上界的条件下,要使得第1个代理目标函数最小化。由于该问题是NP难问题,为该问题给出最优性质刻画和复杂度分析,以及设计了伪多项式动态规划算法。并用算例实验来说明了算法的可行性。

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

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