Int. J. Simul. Multidisci. Des. Optim.
Volume 12, 2021
Computation Challenges for engineering problems
|Number of page(s)||8|
|Published online||09 November 2021|
Ant colony optimization with semi random initialization for nurse rostering problem
Computer Science Department, BINUS Graduate Program − Master of Computer Science, Bina Nusantara University, Jakarta 11480, Indonesia
2 Computer Science Department, School of Computer Science, Bina Nusantara University, Jakarta 11480, Indonesia
* Corresponding author e-mail: email@example.com
Accepted: 20 October 2021
A nurse rostering problem is an NP-Hard problem that is difficult to solve during the complexity of the problem. Since good scheduling is the schedule that fulfilled the hard constraint and minimizes the violation of soft constraint, a lot of approaches is implemented to improve the quality of the schedule. This research proposed an improvement on ant colony optimization with semi-random initialization for nurse rostering problems. Semi-random initialization is applied to avoid violation of the hard constraint, and then the violation of soft constraint will be minimized using ant colony optimization. Semi-random initialization will improve the construction solution phase by assigning nurses directly to the shift that is related to the hard constraint, so the violation of hard constraint will be avoided from the beginning part. The scheduling process will complete by pheromone value by giving weight to the rest available shift during the ant colony optimization process. This proposed method is tested using a real-world problem taken from St. General Hospital Elisabeth. The objective function is formulated to minimize the violation of the constraints and balance nurse workload. The performance of the proposed method is examined by using different dimension problems, with the same number of ant and iteration. The proposed method is also compared to conventional ant colony optimization and genetic algorithm for performance comparison. The experiment result shows that the proposed method performs better with small to medium dimension problems. The semi-random initialization is a success to avoid violation of the hard constraint and minimize the objective value by about 24%. The proposed method gets the lowest objective value with 0,76 compared to conventional ant colony optimization with 124 and genetic algorithm with 1.
Key words: Scheduling / nurse rostering problem / ant colony optimization / optimization
© S. Achmad et al., Published by EDP Sciences, 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.