Abstract
| Language | English |
|---|---|
| Pages | 125-138 |
| Number of pages | 14 |
| Journal | Computers & Operations Research |
| Volume | 65 |
| Early online date | 29 Jul 2015 |
| DOIs | |
| Publication status | Published - 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
}
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 journal › Article
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 -