A Genetic Algorithm for Finding Good Balanced Sequences in a Customer Assignment Problem with no State Information

Wim Hordijk (), Arie Hordijk () and Bernd Heidergott ()
Additional contact information
Wim Hordijk: Lausanne, Switzerland
Arie Hordijk: Mathematical Institute, Leiden University, Niels Bohrweg 1 2333 CA Leiden, The Netherlands
Bernd Heidergott: Tinbergen Institute and Department of Econometrics and Operations Research, Vrije Universiteit Amsterdam, De Boelelaan 1105, Floor II, A-Wing, 1081 HV Amsterdam, The Netherlands

Asia-Pacific Journal of Operational Research (APJOR), 2015, vol. 32, issue 03, 1-20

Abstract: In this paper, we study the control problem of optimal assignment of tasks to servers in a multi-server queue with inhomogeneous servers. In order to improve the performance of the system, we use a periodic deterministic sequence of job assignments to servers called a billiard sequence. We then use a genetic algorithm (GA) for computing a near-optimal billiard sequence. By means of a recent result obtained in the area of ordinal optimization, we show that the solution found by the GA belongs to the top 1% of possible choices for such a billiard sequence. As illustrated by numerical examples, not only is the performance under a billiard sequence better than that of the corresponding randomized policy, the optimal billiard sequence even outperforms the billiard implementation of the optimal randomized policy. The framework we introduce in this paper is suitable for general optimization problems over (periodic) deterministic decision sequences. Given the significant performance improvement that a switch from randomized policies to billiard sequences yields, this framework is of importance in practical applications. Finally, we show that constrained or multi-objective optimization can be dealt with in our framework as well.

Keywords: Control; multi-server queue; billiard sequence; genetic algorithm; ordinal optimization (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595915500153
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:32:y:2015:i:03:n:s0217595915500153

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595915500153

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().