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

Yunqiang Yin, Wen Hung Wu, Edwin Tai Chiu Cheng, Chin Chia Wu, Wen Hsiang Wu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

15 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)2587-2601
Number of pages15
JournalApplied Mathematical Modelling
Volume39
Issue number9
DOIs
Publication statusPublished - 1 Jan 2015

Keywords

  • MBO algorithm
  • Scheduling
  • Two agents

ASJC Scopus subject areas

  • Modelling and Simulation
  • Applied Mathematics

Cite this