Complexity analyses for multi-agent scheduling problems with a global agent and equal length jobs

We study the scheduling of independent jobs where several agents compete to perform their jobs on common identical parallel machines: resource manager GA (global agent) wants to minimize a cost function associated with all jobs, while each agent k wants to have another cost function associated with its jobs not exceeding a given value Qk, k=1,…,K. The jobs have equal processing requirements. Monotonic regular objective functions depending on the completion times of jobs are considered. The global cost function of agent GA may correspond to the global performance of the workshop independently on the agents objective functions. With various combinations of the objective functions, new complexity results are proposed and polynomial algorithms are derived to find an optimal solution that minimizes the global objective function, subject to the constraints that the objective functions of the other agents do not exceed a given threshold.