Acceptance Strategies for Maximizing Agent Profits in Online Scheduling

Abstract

In the market of global logistics, agents need to decide upon whether to accept jobs sequentially offered to them. These jobs, which need to be executed in the near future, have different payments and time constraints. In the offering process we study here, an agent (with limited capacity) needs to make an immediate acceptance decision with little knowledge about future jobs. The goal of the agent is to maximize its profit in such a dynamic environment. We therefore study the online decision problem of acceptance of unit length jobs with time constraints.We consider the problem as a repeated take-it-or-leave-it game which involves online scheduling; we design strategies for when to accept an offered job. Specifically, we present theoretically optimal strategies for a fundamental case, and develop heuristic strategies in combination with an evolutionary algorithm for more general and complex cases. We show experimentally that in the fundamental case the performance of our heuristic solutions is almost the same as that of the theoretical solutions. In various settings, we compare the results achieved by our online solutions to those generated by the optimal offline solutions; the average-case performance ratios are about 1.1. We also analyze the impact of the ratio between the number of slots and the number of jobs on the difficulty of decisions and the performance of our solutions. Although we use a relatively simple scheduling problem to illustrate our approach, we show that it generalizes to online acceptance of jobs in more complex scheduling scenarios as well.