重庆师范大学 数学科学学院,重庆 401331;贵州工程应用技术学院 经济与管理学院,贵州 毕节 551700
【目的】研究与误工相关的两个代理单机排序问题。【方法】第一个代理工件的到达时间与工期满足一致关系,目标函数为总误工或最大误工。第二个代理工件可中断,目标函数为总误工工件个数,在模型确定的情况下结合Lawler算法或EDD规则确定一个最优排序规则,使得满足第二个代理目标可行的情况下,第一个代理的目标函数值最小。【结果】在上述模型最优排序规则确定的前提下,求出最优排序方案使得第一个代理的目标函数最小。【结论】提出了总误工问题的一个拟多项式时间动态规划算法,给出了最大误工问题时间复杂度的证明。
张新功,陈秋宏,王祥兵 .关于误工的两个代理单机排序问题 [J].重庆师范大学学报自然科学版,2018,(4):1-