A honey-bees optimization algorithm for a two-agent single-machine scheduling problem with ready times

In this paper we consider two agents that compete on the use of a common processor. Each of the agents has a set of jobs that have to be processed on the same machine without preemption. Each of the agents wants to minimize an objective function that depends on the completion time of its own jobs. In addition, each job has different release dates. In the presence of unequal release dates, it is sometimes advantageous to form a non-full batch, while in other situations it is a better strategy to wait for future job arrivals in order to increase the fullness of the batch. The objective is to find a schedule that performs well with respect to the objectives of both agents. To solve this difficulty problem, we construct a branch-and-bound solution scheme incorporating these bounds and some dominance rules for the optimal solution. In view of the advantage of combining local and global searches in the honey-bees optimization algorithm, we attempt to use a marriage in honey-bees optimization algorithm (MBO) to find near-optimal solutions. We conduct extensive computational experiments to evaluate the performance of the algorithms.