何 程，韓鑫鑫

(河南工業(yè)大學 理學院，河南 鄭州 450001)

1 引言

多代理排序問題是Baker和Smith[2]最先引入的。 有幾個代理，每個代理有一個工件集和一個目標函數(shù)。這些代理的工件必須在一個共同的加工資源(例如，一臺機器)上被加工，并且每個代理都希望最小化各自的目標函數(shù)，每個代理的目標函數(shù)只與他自己工件的完工時間相關(guān)。我們的問題是找到一個滿足每個代理的目標函數(shù)要求的排序。

多代理排序問題起源于需要多方協(xié)商解決問題的情形。它在工業(yè)管理、電信服務(wù)等方面應(yīng)用廣泛 (見[4]和[9])。 現(xiàn)在多代理排序問題已被廣泛研究。Agnetis等人[1]研究了單機多代理排序問題，他們考慮的目標函數(shù)是正則函數(shù)(單調(diào)非減函數(shù))的最大值，誤工工件數(shù)和加權(quán)總完工時間。Cheng等人[3]和原晉江[10]也研究了單機上的多代理排序問題。Leung等[8]研究了兩個代理的一致平行機排序問題。

本文考慮序列分批模型，該模型中，工件被分批加工，并且同一批工件具有相同的開工時間和完工時間，每批工件的加工時間等于該批中所有工件的加工時間和，且加工每一批工件前，機器都有一個安裝時間。對于同時最小化A代理的時間表長和B代理的最大延遲的無界序列分批排序問題，馮琪等[5]給出了一個多項式時間算法來找到該問題的所有Pareto最優(yōu)解。對于Pareto最優(yōu)排序問題1|s-batch,b

2 預備知識

3 Pareto最優(yōu)算法

(3.1)

(3.2)

因此我們有下列引理。

由上述算法，我們可以通過下面的算法POP找到所有的Pareto最優(yōu)點。

算法POP

[參考文獻]

[1]A. Agnetis, D. Pacciarelli, A.Pacifici, Multi-agent single machine scheduling[J]. Ann. Oper. Res.,2007,(150) :3-15.

[2]K.R. Baker, J.C. Smith, A multiple-criterion model for machine scheduling[M]. Journal of Scheduling, 2003,(6) :7-16.

[3]T.C.E. Cheng, C.T. Ng, J.J. Yuan. Multi-agent scheduling on a single machine with max-form criteria[J]. Eur. J. Oper. Res., 2008,(188):603-609.

[4]I. Curiel, G. Pederzoli, S. Tijs, Sequencing games[J]. Eur.J. Oper. Res., 1989, (40)344-351.

[5]Q. Feng, Z.Y. Yu, W.P. Shang, Pareto optimization of serial-batching scheduling problems on two agents[C]. ICAMechS, ISBN 978-1-4577-1698-0.

[6]R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey[J]. Annals of Discrete Mathematics, 1979, (5):287-326.

[7]C. He, H. Lin, Y.X. Lin, Bounded serial-batching scheduling for minimizing maximum lateness and makespan[J]. Discr. Opti., 2015,(16): 70-75.

[8]J. Y. -T. Leung, M. Pinedo, G. Wan, Competitive two-agent scheduling and its applications[J]. Oper. Res. 2010,(58):458-469.

[9]D. Schultz, S. H. Oh, C. F. Grecas, M. Albani, J. Sanchez,C. Arbib, V. Arvia, M. Servilio, F. Del Sorbo, A. Giralda, G.Lombardi, A QoS concept for packet oriented SUMTS services[M]. In: Proceedings of the 1st Mobile Summit, Thessaloniki, Greec (2002).

[10]J.J. Yuan, Complexities of some problems on multi-agent scheduling on a single machine[J].J. Oper. Res. Soc. China, 2016,(4):379-384.