The scheduling problems in which agents have to share the same set(s) of resources are at the frontier of combinatorial optimization and cooperative game theory. This problem is NP-hard. In this paper, we consider two objective functions: minimize the makespan (the completion time) of one agent and minimize the total number of tardy jobs with a common due date of the other agents. We proposed polynomial heuristics, combined heuristic with integer linear programming and combined heuristic with simulated annealing, Tabu search, and matheuristic. Experimental results are conducted to measure the solution quality given by lower bound, heuristics and the metaheuristics.
Keywords: Multi-criteria optimization, multi-agent scheduling, parallel machines, heuristics, metaheuristics, mixed integer linear programming, simulated annealing, Tabu search, matheuristic, total number of tardy job and makespan.