Sort Of Multi-objective Results

Scheduling has wide practical application background. Multicriteria scheduling is one of the important branches of scheduling. In the multicriteria scheduling, we have two or more objective functions, and the target is to seek a schedule such that all the objective functions are optimized or satisfied.Multi-agent scheduling is a new research topic in the multicriteria scheduling. In this model, we have m > 2 agents(customers) having job sets J₁ ,J₂,..., J_m, respectively. All the jobs must be processed in a common machine with the restriction that the machine can process one job at each time moment. Suppose that the objective function of agent i is ri, 1 ≤ i ≤ m. The reseached problems include the following forms.in this problem, we seek a schedule such that the total weighted objective function of the agents is optimized. This problem is also denoted by.this problem, m = 2, we seek a schedule such that the value of r1 is optimized subject to the condition that the value of r2 is satisfied.The works of this paper are the development of the research works of Baker, Smith, Agentis etc. The objective functions to be researched include C_max, ΣCj, L_max, max WjCj, ΣWjCj and max Vj. The main results of this paper are as follows.Theorem 1 The problem 1 || ΣCi + max W'iG'i can be solved in polynomial time. The following is the algorithm.Step 1 Set u := n1, v := n2 and F: =0.Step 2 If u = 0, then define π(i) = J'i, 1 ≤ i ≤ v and stop.Step 3 If v = 0, then define π(i) = Ji, 1 ≤ i ≤ u, set F := F + Σ t(i, 0) and stop.Step 4 If max W'vt(u, v) > y, then define max W'vt(u, v) ≤ y, then define π(u+v) — J'v and set v :=v — 1; return to Step 2.Theorem 2 The problem 1 || EC* : maxWj'Cj- can be solved in polynomial time. The following is the algorithm.Step 1 Set u :— n\, v := n2.Step 2 If u = 0, then define ir(i) = J-, 1 < i < v and stop.Step 3 If v — 0, then define ir(i) = Jh 1 < i < u and stop.Step 4 If max W'vt(u, v) > y, then define tt(u + u) = Ju and set ? :— u - 1 return to Step 2. If max W'vt{u, v) < y, then define tt(u + v) = J'v and set v := v - 1; return to Step 2.Theorem 3 Problem 1|| E W^Q + maxWjCj is strongly NP- hard.Theorem 4 Problem 1|| ￡ WjC,- < Q : E ^' < 0 is strongly NP-hard.Theorem 5 Problem 1|| E WjCj + W max Vj is strongly NP-hard.Theorem 6 Problem 1 || (CgL, Cgl, ■ ■ ■, C^, L￡>J can be solved in polynomial time, where 8^=1.Theorem 7 Problem 1 || (C^, ? ? ?, C￡L, E WJr+1)C^+1), ■ ■ ■, E WJk)C$k)) can be solved in polynomial time.Theorems Problem 1 || (￡Wf >Cf,￡Wf >Cf >, ■ ■ ? ^WJ"-^"^, L^\C^) is strongly NP- hard.Theorem 9 Problem 1 || (E C^>, E C(2), ? ■ ■, ￡ C^"1), Z,Mj is NP-hard.