Fixed Jobs Multi-agent Scheduling Problem with Renewable Resources

摘要

We consider multi-agent scheduling problem where the set of jobs to schedule is divided into two disjoint subsets A and B. Each subset of jobs is associated to one agent. The two agents compete to perform their independent jobs without preemption on common m identical parallel machines. Each machine has limited renewable resource units R_k, k = 1... K necessary to perform each job. The start date, fixed finish date and required additional resources are given and fixed. A machine can process more than one job at a time provided the resource consumption does not exceed R_k. The objective is to determine a feasible schedule that maximizes the number of scheduled jobs of agent A, while keeping the number of scheduled jobs of agent B no less than a fixed value Q_b , or equivalently the agents aims at minimizing the number of their rejected jobs. This problem is called a Competing multi-agent scheduling. The problem under study is NP-hard. To obtain best compromise solutions for each agent, integer linear programming model and greedy heuristics based on ε-constraint approach are proposed to compute exact and approximate Pareto fronts. A Non-dominated Sorting Genetic Algorithm (NSGA-II) is developed to generate Pareto front. Experimental results are driven to analyse the performances of the proposed methods.