摘要
多目标排序是排序论的一个重要分支,在解决经济、管理、工程、军事、社会等领域出现的复杂问题中起着越来越重要的作用。本文研究以误工个数∑Uj为第1目标,∑wjCj或者∑wjTj为第2目标的多重目标排序问题,分别给出了这两个问题在不误工工件集不改变下工件加工时间和权重满足反一致性条件(pi≤pjwi≥wj)时复杂性为O(nlogn)的多项式时间算法:对于排序问题1│(pi≤pj)(wi≥wj)│(∑wjCj/E),选取排序最后一个工件k满足条件:pk/wk=max{pi/wi│i∈M∪L};对于排序问题1│(pi≤pj)(wi≥wj)│(∑wjTj/E),选取排序最后一个工件k满足:1)若M为空集,pk/wk=max{pi/wi│i∈L};2)若M非空,任意选取k∈M。其中L是误工工件集,M是放在最后不误工的工件的集合。最后,证明了这两个算法可以得到相应问题的最优解。
Scheduling problems with multiple objectives play increasing important roles in solving complicated problems appearing in the fields of economy, management, engineering, military affairs and society etc. In this paper, we give two polynomial-time algorithms when all tardy jobs are given for the two binary NP-hard problems 1|| Lex( ∑Uj, ∑wjCj) and 111 Lex( ∑Uj, ∑wjCj). For the problem 1 | pi≤Pj→≥wi≥wj| Lex(E, ∑, wjCJ), schedule job k last, where pk/wk = max {pi/wi ] i∑ M ∪ L} , and M = i | di≥∑i∈Jpi| is the set of jobs which are not tardy even when processed last, L is set of tardy jobs; For the problem 1 | pi≤pj)→(wi≥wj|Lex(E, ∑wjTj),schedule job k last, where pk/wk = max {pi/wi | i∈ L} if M is empt; else choose any job in M. In the end, we give prooves of the schedule which got from the polynomial-time algorithm is an optimal solution for the scheduling problem with weighted agreeable condition resprctively.
出处
《重庆师范大学学报(自然科学版)》
CAS
2010年第2期4-8,共5页
Journal of Chongqing Normal University:Natural Science
基金
国家自然科学基金项目(No.70731160015
No.0710015)
运筹学与系统工程重庆市市级重点实验室资助(No.YC200802)
关键词
排序
误工
算法
多目标
计算复杂性
最优性
scheduling
tardy
algorithm
multiple objectives
complexity
optimality