两个多重目标排序问题的多项式时间算法

Two Polynomial-Time Algorithms for Dual Scheduling Problems

多目标排序是排序论的一个重要分支,在解决经济、管理、工程、军事、社会等领域出现的复杂问题中起着越来越重要的作用。本文研究以误工个数∑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.