Ant colony optimization with semi random initialization for nurse rostering problem
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 s...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
EDP Sciences
2021-01-01
|
| Series: | International Journal for Simulation and Multidisciplinary Design Optimization |
| Subjects: | |
| Online Access: | https://www.ijsmdo.org/articles/smdo/full_html/2021/01/smdo210083/smdo210083.html |
| _version_ | 1818402791072202752 |
|---|---|
| author | Achmad Said Wibowo Antoni Diana Diana |
| author_facet | Achmad Said Wibowo Antoni Diana Diana |
| author_sort | Achmad Said |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-14T08:13:58Z |
| format | Article |
| id | doaj.art-1f816243fcf8476c9c8f7aa3f8e0436a |
| institution | Directory Open Access Journal |
| issn | 1779-6288 |
| language | English |
| last_indexed | 2024-12-14T08:13:58Z |
| publishDate | 2021-01-01 |
| publisher | EDP Sciences |
| record_format | Article |
| series | International Journal for Simulation and Multidisciplinary Design Optimization |
| spelling | doaj.art-1f816243fcf8476c9c8f7aa3f8e0436a2022-12-21T23:10:00ZengEDP SciencesInternational Journal for Simulation and Multidisciplinary Design Optimization1779-62882021-01-01123110.1051/smdo/2021030smdo210083Ant colony optimization with semi random initialization for nurse rostering problemAchmad Said0https://orcid.org/0000-0002-9537-2311Wibowo Antoni1Diana Diana2Computer Science Department, BINUS Graduate Program − Master of Computer Science, Bina Nusantara UniversityComputer Science Department, BINUS Graduate Program − Master of Computer Science, Bina Nusantara UniversityComputer Science Department, School of Computer Science, Bina Nusantara UniversityA 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.https://www.ijsmdo.org/articles/smdo/full_html/2021/01/smdo210083/smdo210083.htmlschedulingnurse rostering problemant colony optimizationoptimization |
| spellingShingle | Achmad Said Wibowo Antoni Diana Diana Ant colony optimization with semi random initialization for nurse rostering problem International Journal for Simulation and Multidisciplinary Design Optimization scheduling nurse rostering problem ant colony optimization optimization |
| title | Ant colony optimization with semi random initialization for nurse rostering problem |
| title_full | Ant colony optimization with semi random initialization for nurse rostering problem |
| title_fullStr | Ant colony optimization with semi random initialization for nurse rostering problem |
| title_full_unstemmed | Ant colony optimization with semi random initialization for nurse rostering problem |
| title_short | Ant colony optimization with semi random initialization for nurse rostering problem |
| title_sort | ant colony optimization with semi random initialization for nurse rostering problem |
| topic | scheduling nurse rostering problem ant colony optimization optimization |
| url | https://www.ijsmdo.org/articles/smdo/full_html/2021/01/smdo210083/smdo210083.html |
| work_keys_str_mv | AT achmadsaid antcolonyoptimizationwithsemirandominitializationfornurserosteringproblem AT wibowoantoni antcolonyoptimizationwithsemirandominitializationfornurserosteringproblem AT dianadiana antcolonyoptimizationwithsemirandominitializationfornurserosteringproblem |