کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475043 | 699196 | 2016 | 14 صفحه PDF | دانلود رایگان |
• Proposed GDPSO combines min-conflict strategy, random walk and genetic operators.
• Proposed GDPSO outperforms in stability and efficiency than MCRW, TS, GGA, and SPSO.
• Proposed GDPSO has a faster and consistent rate of convergence.
• Proposed GDPSO results in superior performance to solve complex timetabling problem.
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.
Journal: Computers & Operations Research - Volume 65, January 2016, Pages 125–138