Optimal Algorithms for Two Agent Parallel Batch Scheduling with Rejection

Abstract

Efficient scheduling can make full use of resource, and achieve many goals, such as maximizing efficiency and saving energy. The scheduling problems involving two agents and rejection to perform their respective jobs on a parallel batch machine are considered. The manager need to choose the jobs for processing and arrange its schedule. The objective is to minimizes the objective of first agent, and keep the other agent’s objective below a given threshold. Three objective functions in scheduling theory are studied, and we analyze the problem complexity and give optimal algorithms for three problems. The optimal algorithms can help the manager to reduce the production time and cost.