LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:

OpenAIRE is about to release its new face with lots of new content and services.
During September, you may notice downtime in services, while some functionalities (e.g. user registration, login, validation, claiming) will be temporarily disabled.
We apologize for the inconvenience, please stay tuned!
For further information please contact helpdesk[at]openaire.eu

fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Goodman, Melissa Dee
Languages: English
Types: Doctoral thesis
Subjects: QA
This thesis investigates the idea of balancing different constraints in order to find optimal solutions to two personnel scheduling problems, within the framework of constructive metaheuristic approaches. The two problems considered are a nurse scheduling problem, for which finding feasible solutions is known to be difficult and for which the hard and soft constraints are in direct conflict, and a medical student scheduling problem for which there is little relevant literature this second problem also has conflicting hard and soft constraints, but presents further conflict between the different soft constraints. The methods used to solve these problems are focused on two constructive metaheuristics in particular: Greedy Randomised Adaptive Search Procedures (GRASP) and Ant Colony Optimisation (ACO) and for each approach several construction heuristics are introduced and compared. Using GRASP, a number of local search neighbourhoods are established for each problem, while for ACO the suitability of three trail definitions are compared. In order to further explore the balance which may obtained between the different constraints and objectives for the two problems, hybrid constructions are investigated, incorporating exact methods which take advantage of the underlying structures of each problem with regards to feasibility. For medical student scheduling, this exact method was developed into a new type of construction mechanism providing much improved results over a standard heuristic approach. Further enhancements investigated include the use of problem-specific feedback for nurse scheduling and the use of an intelligent memory procedure for the medical student scheduling problem. For the nurse scheduling problem, the final algorithm developed was able to rival the best in the literature so far and produce optimal solutions for all available datasets. For the medical student scheduling problem, optimal solutions are not known, but the results obtained are very promising and provide a good basis for further study of the problem.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • Appendix A - Nurse scheduling datasets..............................................314 A. 1 Sample dataset............................................................................................... 327 Appendix B - Calculation of nurse preference costs..........................331 Appendix E - Tabu search..................................................................... 341 Appendix F - Genetic algorithms..........................................................343 Appendix G - Paper accepted for publication.....................................345 Chapter 2 - Introduction to problems Figure 2.1 An example of an nxn Latin square with entries a# = i..................29 Figure 2.2 Latin rectangle setup of the medical student scheduling problem for specialities 2 - 5 ........................................................................ 30 Figure 2.3 Example demonstrating how using a group-rotation approach to guarantee feasibility may result in higher than necessary student pair costs.......................................................................................... 35 Abramson, D. (1991). “Constructing school timetables using simulated annealing: sequential and parallel algorithms”, Man. Sci., 37, 98-113.
    • Aickelin, U. and K. A. Dowsland (2000). “Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem,” J. Sched., 3, 139-153.
    • Aickelin, U. and K. A. Dowsland (2004). “An Indirect Genetic Algorithm for a nursescheduling problem,” Comput. Oper. Res. 31, 761-778.
    • Aickelin, U. and J. Li (2007). “An Estimation of Distribution Algorithm for Nurse Scheduling,” to appear in Annals o f Oper. Res.
    • Aiex, R.M., S. Binato, and M.G.C. Resende (2003). “Parallel GRASP with pathrelinking for job shop scheduling,” Parallel Computing 29, 393-430.
    • Bellanti, F., G. Carello, F. Della Croce, and R. Tadei (2004). “A greedy-based neighbourhood search approach to a nurse rostering problem,” Eur. J. Oper. Res. 153, 28-40.
    • Berrada, I., J. A. Ferland, and P. Michelon (1996). “A Multi-objective Approach to Nurse Scheduling with both Hard and Soft Constraints,” Socio-Economic Planning Sciences, 30, 183-193.
    • Binato, S., W. J. Hery, D. M. Loewenstem and M. G. C. Resende (2001). “A GRASP for job shop scheduling”, Essays and surveys in metaheuristics, 15, 81-100.
    • Brusco, M.J. and L. W. Jacobs (1995). “Cost Analysis of Alternative Formulations for Personnel Scheduling in Continuous Operating Organizations.” Eur. J. Oper. Res 86, 249-261.
    • Burke, E., P. Cowling, P. De Causmaecker and G.Vanden Berghe (2001). “A Memetic Approach to the Nurse Rostering Problem ”, Applied Intelligence, 15, No. 3, 199-214.
    • Burke, E., P. De Causemaecker, S. Petrovic, and G. Vanden Berghe (2003a), “Variable Neighbourhood Search for Nurse Rostering Problems”, In Mauricio G. C. Resende and Jorge Pinho de Sousa (eds.), METAHEURISTICS: Computer DecisionMaking, Chapter 7, Kluwer, pp. 153-172.
    • Burke, E., P. De Causemaecker and G. Vanden Berghe (1999). “A Hybrid Tabu Search Algorithm for the Nurse Rostering Problem”, in B. McKay et al. (eds.), Simulated Evolution and Learning, Springer, Lecture Notes in Artificial Intelligence, Vol. 1585, pp.187-194 .
    • Burke, E., P. De Causemaecker, G. Vanden Burghe and H. Van Landeghem (2004). “The State of the Art of Nurse Rostering,” J. Sched., 1, 441-499.
    • Burke, E., G. Kendall and E. Soubeiga (2003b). “A Tabu-Search Hyperheuristic for Timetabling and Rostering,” J. Heuristics 9, 451-470.
    • Cheang, B., H. Li, A. Lim and B. Rodrigues (2003). “Nurse rostering problems - a bibliographic survey,” Eur. J. Oper. Res. 151, 447-460.
    • Dowsland, K. A. (1998) “Nurse scheduling with tabu search and strategic oscillation.” Eur. J. Oper. Res. 106, 393-407.
    • Dowsland, K. A. and J. M. Thompson (2000). “Solving a nurse-scheduling problem with knapsacks, networks and tabu search,” J. Oper. Res. Soc. 51, 825-833.
    • Drexl, A. and F. Salewski (1997). “Distribution requirements and compactness constraints in school timetabling”, Eur. J. Oper. Res. 102, 193-214.
    • Ernst, T., H. Jiang, M. Krishnamoorthy, and D. Sier (2004). “Staff scheduling and rostering: A review of applications, methods and models,” Eur. J. Oper. Res. 153, 3- 27.
    • Feo, T. A., M. G. C. Resende and S.H. Smith (1994). “A greedy randomised adaptive search procedure for maximum independent set,” Oper. Res. 42, 860-878.
    • 40 50 60 average %feasible 40 50 60 average %feasible
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article

Cookies make it easier for us to provide you with our services. With the usage of our services you permit us to use cookies.
More information Ok