A genetic algorithm for finding good balanced sequences in a customer assignment problem with no state information

W. Hordijk, A. Hordijk, B.F. Heidergott

Research output: Contribution to JournalArticleAcademicpeer-review

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.
Original languageEnglish
Article number6
Number of pages20
JournalAsia-Pacific Journal of Operational Research
Volume32
Issue number3
DOIs
Publication statusPublished - 2015

Fingerprint

Assignment problem
Genetic algorithm
Optimization problem
Performance improvement
Job assignment
Multi-server queues
Multi-objective optimization
Assignment

Cite this

@article{a7499d877ddc44e581182c20f10e7be5,
title = "A genetic algorithm for finding good balanced sequences in a customer assignment problem with no state information",
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.",
author = "W. Hordijk and A. Hordijk and B.F. Heidergott",
year = "2015",
doi = "10.1142/S0217595915500153",
language = "English",
volume = "32",
journal = "Asia-Pacific Journal of Operational Research",
issn = "0217-5959",
publisher = "World Scientific Publishing Co. Pte Ltd",
number = "3",

}

A genetic algorithm for finding good balanced sequences in a customer assignment problem with no state information. / Hordijk, W.; Hordijk, A.; Heidergott, B.F.

In: Asia-Pacific Journal of Operational Research, Vol. 32, No. 3, 6, 2015.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - A genetic algorithm for finding good balanced sequences in a customer assignment problem with no state information

AU - Hordijk, W.

AU - Hordijk, A.

AU - Heidergott, B.F.

PY - 2015

Y1 - 2015

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

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

U2 - 10.1142/S0217595915500153

DO - 10.1142/S0217595915500153

M3 - Article

VL - 32

JO - Asia-Pacific Journal of Operational Research

JF - Asia-Pacific Journal of Operational Research

SN - 0217-5959

IS - 3

M1 - 6

ER -