Loading…

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

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...

Full description

Saved in:
Bibliographic Details
Published in:Asia-Pacific journal of operational research 2015-06, Vol.32 (3), p.1550015
Main Authors: Hordijk, Wim, Hordijk, Arie, Heidergott, Bernd
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0217-5959
1793-7019
0217-5959
DOI:10.1142/S0217595915500153