郑州大学学报（理学版）
鄭州大學學報（理學版）
정주대학학보（이학판）
JOURNAL OF ZHENGZHOU UNIVERSITY(NATURAL SCIENCE EDITION)
2009年
4期
21-26
,共6页
重新排序%多代理%目标函数%延迟%错位
重新排序%多代理%目標函數%延遲%錯位
중신배서%다대리%목표함수%연지%착위
rescheduling%multiagent%objective function%lateness%disruption
两个代理的重新排序问题是指,每一个代理有一个非中断加工的工件集,两个代理共用一个机器进行加工,每一个代理分别考察依赖于各自工件完工时间的目标函数.针对单机上有限错位和原始工件集最大延迟限制下,使得新工件集的最大延迟或总加工时间和最小的多代理重新排序问题,设计出几个这类问题的多项式或拟多项式时间的算法.
兩箇代理的重新排序問題是指,每一箇代理有一箇非中斷加工的工件集,兩箇代理共用一箇機器進行加工,每一箇代理分彆攷察依賴于各自工件完工時間的目標函數.針對單機上有限錯位和原始工件集最大延遲限製下,使得新工件集的最大延遲或總加工時間和最小的多代理重新排序問題,設計齣幾箇這類問題的多項式或擬多項式時間的算法.
량개대리적중신배서문제시지,매일개대리유일개비중단가공적공건집,량개대리공용일개궤기진행가공,매일개대리분별고찰의뢰우각자공건완공시간적목표함수.침대단궤상유한착위화원시공건집최대연지한제하,사득신공건집적최대연지혹총가공시간화최소적다대리중신배서문제,설계출궤개저류문제적다항식혹의다항식시간적산법.
The rescheduling problem on two agents is considered,each with a set of nonpreemptive jobs,and the two competing to perform their respective jobs on a common processing resource.Each agent wants to minimize a certain objective function,which only depends on the completion time of its jobs.The two agents rescheduling problem for jobs on a single machine is considered to minimize maximum lateness or total completion time under a limit on the lateness of the original jobs.It is shown that the considered problems can be solved either in polynomial time or in pseudopolynomial time.
