总迟后相关的两个工况代理的单机排序问题  

Two-agent Scheduling Problem of Working Condition with Total Late Work on a Single Machine

作　　者：戴秦[1,2] 郑兴山[3] 张新功[4] 严广乐[1] 

机构地区：[1]上海理工大学管理学院,上海200093 [2]上海电力学院经济管理系,上海200090 [3]上海交通大学安泰经济与管理学院,上海200240 [4]重庆师范大学数学学院,重庆401331

出　　处：《工业工程与管理》2014年第6期78-82,88,共6页Industrial Engineering and Management

基　　金：上海高校一流学科建设项目(S1201YLXK);教育部课题(Z2011-099)

摘　　要：研究了两个代理的单机排序问题。其中一个代理以工件总迟后相关的为目标函数(总迟后和加权总迟后),第二个代理以最大费用函数为目标函数。排序问题的目标就是寻找一个序列,使得在第二个代理的目标函数不超过给定的上界的情况下,第一个代理的目标函数最小。对于总迟后的情形,并给出拟多项式时间的动态规划算法。当第一个代理中的工件具有相等工期时,考虑了加权总迟后问题,并给出了一个多项式时间算法。最后对于总迟后问题给数值实验。In this paper, two-agent scheduling problem is presented. The first agent has total late work as its objective function（total late work and total weighted late work）, and the second agent has the maximum cost as its objective function. The goal of the proposed problem is to find a schedule that the objective function of agent A is minimized, subject to the requirement that the objective function of agent B cannot exceed a given bound U. We present a pseudo-polynomial time algorithm to solve the scheduling problem with total late work. If the jobs of the agent A have the same due date,we give a polynomial time algorithm. Finally, a computational experience is given.

关 键 词：排序 两个代理 动态规划算法 迟后 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置] O223[自动化与计算机技术—控制科学与工程]