Genetic based discrete particle swarm optimization for elderly day care center timetabling

M.Y. Lin, K.S. Chin, K.L. Tsui, T.C. Wong

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

The timetabling problem of local Elderly Day Care Centers (EDCCs) is formulated into a weighted maximum constraint satisfaction problem (Max-CSP) in this study. The EDCC timetabling problem is a multi-dimensional assignment problem, where users (elderly) are required to perform activities that require different venues and timeslots, depending on operational constraints. These constraints are categorized into two: hard constraints, which must be fulfilled strictly, and soft constraints, which may be violated but with a penalty. Numerous methods have been successfully applied to the weighted Max-CSP; these methods include exact algorithms based on branch and bound techniques, and approximation methods based on repair heuristics, such as the min-conflict heuristic. This study aims to explore the potential of evolutionary algorithms by proposing a genetic-based discrete particle swarm optimization (GDPSO) to solve the EDCC timetabling problem. The proposed method is compared with the min-conflict random-walk algorithm (MCRW), Tabu search (TS), standard particle swarm optimization (SPSO), and a guided genetic algorithm (GGA). Computational evidence shows that GDPSO significantly outperforms the other algorithms in terms of solution quality and efficiency.
LanguageEnglish
Pages125-138
Number of pages14
JournalComputers & Operations Research
Volume65
Early online date29 Jul 2015
DOIs
Publication statusPublished - Jan 2016

Fingerprint

Timetabling
Discrete Optimization
Particle swarm optimization (PSO)
Particle Swarm Optimization
Constraint satisfaction problems
Constraint Satisfaction Problem
Tabu search
Heuristics
Soft Constraints
Evolutionary algorithms
Tabu Search Algorithm
Repair
Branch-and-bound
Exact Algorithms
Assignment Problem
Genetic algorithms
Approximation Methods
Penalty
Evolutionary Algorithms
Random walk

Keywords

  • weighted max-constraint satisfaction problem
  • discrete particle swarm optimization
  • genetic algorithm
  • min-conflict random walk
  • tabu search
  • timetabling problem

Cite this

@article{9c1339a8c5df4b81ae0621d64a67b6f7,
title = "Genetic based discrete particle swarm optimization for elderly day care center timetabling",
abstract = "The timetabling problem of local Elderly Day Care Centers (EDCCs) is formulated into a weighted maximum constraint satisfaction problem (Max-CSP) in this study. The EDCC timetabling problem is a multi-dimensional assignment problem, where users (elderly) are required to perform activities that require different venues and timeslots, depending on operational constraints. These constraints are categorized into two: hard constraints, which must be fulfilled strictly, and soft constraints, which may be violated but with a penalty. Numerous methods have been successfully applied to the weighted Max-CSP; these methods include exact algorithms based on branch and bound techniques, and approximation methods based on repair heuristics, such as the min-conflict heuristic. This study aims to explore the potential of evolutionary algorithms by proposing a genetic-based discrete particle swarm optimization (GDPSO) to solve the EDCC timetabling problem. The proposed method is compared with the min-conflict random-walk algorithm (MCRW), Tabu search (TS), standard particle swarm optimization (SPSO), and a guided genetic algorithm (GGA). Computational evidence shows that GDPSO significantly outperforms the other algorithms in terms of solution quality and efficiency.",
keywords = "weighted max-constraint satisfaction problem, discrete particle swarm optimization, genetic algorithm, min-conflict random walk, tabu search, timetabling problem",
author = "M.Y. Lin and K.S. Chin and K.L. Tsui and T.C. Wong",
year = "2016",
month = "1",
doi = "10.1016/j.cor.2015.07.010",
language = "English",
volume = "65",
pages = "125--138",
journal = "Computers & Operations Research",
issn = "0305-0548",

}

Genetic based discrete particle swarm optimization for elderly day care center timetabling. / Lin, M.Y.; Chin, K.S.; Tsui, K.L.; Wong, T.C.

In: Computers & Operations Research, Vol. 65, 01.2016, p. 125-138.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Genetic based discrete particle swarm optimization for elderly day care center timetabling

AU - Lin, M.Y.

AU - Chin, K.S.

AU - Tsui, K.L.

AU - Wong, T.C.

PY - 2016/1

Y1 - 2016/1

N2 - The timetabling problem of local Elderly Day Care Centers (EDCCs) is formulated into a weighted maximum constraint satisfaction problem (Max-CSP) in this study. The EDCC timetabling problem is a multi-dimensional assignment problem, where users (elderly) are required to perform activities that require different venues and timeslots, depending on operational constraints. These constraints are categorized into two: hard constraints, which must be fulfilled strictly, and soft constraints, which may be violated but with a penalty. Numerous methods have been successfully applied to the weighted Max-CSP; these methods include exact algorithms based on branch and bound techniques, and approximation methods based on repair heuristics, such as the min-conflict heuristic. This study aims to explore the potential of evolutionary algorithms by proposing a genetic-based discrete particle swarm optimization (GDPSO) to solve the EDCC timetabling problem. The proposed method is compared with the min-conflict random-walk algorithm (MCRW), Tabu search (TS), standard particle swarm optimization (SPSO), and a guided genetic algorithm (GGA). Computational evidence shows that GDPSO significantly outperforms the other algorithms in terms of solution quality and efficiency.

AB - The timetabling problem of local Elderly Day Care Centers (EDCCs) is formulated into a weighted maximum constraint satisfaction problem (Max-CSP) in this study. The EDCC timetabling problem is a multi-dimensional assignment problem, where users (elderly) are required to perform activities that require different venues and timeslots, depending on operational constraints. These constraints are categorized into two: hard constraints, which must be fulfilled strictly, and soft constraints, which may be violated but with a penalty. Numerous methods have been successfully applied to the weighted Max-CSP; these methods include exact algorithms based on branch and bound techniques, and approximation methods based on repair heuristics, such as the min-conflict heuristic. This study aims to explore the potential of evolutionary algorithms by proposing a genetic-based discrete particle swarm optimization (GDPSO) to solve the EDCC timetabling problem. The proposed method is compared with the min-conflict random-walk algorithm (MCRW), Tabu search (TS), standard particle swarm optimization (SPSO), and a guided genetic algorithm (GGA). Computational evidence shows that GDPSO significantly outperforms the other algorithms in terms of solution quality and efficiency.

KW - weighted max-constraint satisfaction problem

KW - discrete particle swarm optimization

KW - genetic algorithm

KW - min-conflict random walk

KW - tabu search

KW - timetabling problem

UR - http://www.sciencedirect.com/science/article/pii/S030505481500177X

U2 - 10.1016/j.cor.2015.07.010

DO - 10.1016/j.cor.2015.07.010

M3 - Article

VL - 65

SP - 125

EP - 138

JO - Computers & Operations Research

T2 - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

ER -