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

9 Citations (Scopus)
86 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)125-138
Number of pages14
JournalComputers & Operations Research
Volume65
Early online date29 Jul 2015
DOIs
Publication statusPublished - Jan 2016

    Fingerprint

Keywords

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

Cite this