Optimization of the Patients Appointments in Chemotherapy Treatment Unit: Heuristic and Metaheuristic Approaches by Sanjana Shahnawaz A Thesis submitted to the Faculty of Graduate Studies of The University of Manitoba in partial fulfilment of the requirements of the degree of MASTER OF SCIENCE Department of Mechanical and Manufacturing Engineering University of Manitoba Winnipeg Copyright © 2012 by Sanjana Shahnawaz Abstract This research aims to improve the performance of the service of a Chemotherapy Treat- ment Unit by reducing the waiting time of patients within the unit. In order to fulfill the objective, initially, the chemotherapy treatment unit is deduced as an identical parallel machines scheduling problem with unequal release time and single resource. A mathe- matical model is developed to generate the optimum schedule. Afterwards, a Tabu search (TS) algorithm is developed. The performance of the TS algorithm is evaluated by com- paring results with the mathematical model and the best results of benchmark problems reported in the literature. Later on, an additional resource is considered which converted the problem into a dual resources scheduling problem. Three approaches are proposed to solve this problem; namely, heuristics, a Tabu search algorithm with heuristic (TSHu), and Tabu search algorithm for dual resources (TSD). i Acknowledgments First and foremost, I would like to express my gratitude to my thesis supervisors, Dr. Tarek ElMekkawy and Dr. Qingjin Peng for their support, guidance and supervision. Their help, advice and patience have been invaluable on both an academic and a personal level, for which I am extremely grateful. I would like to thank Sue Bates, Director of Patient Navigation, CancerCare Manitoba for her continuous support. Finally, without the financial support of CancCare Manitoba, this research will not be achieved. I also appreciate the co-operation of the committee members who attended the thesis de- fence. ii Dedication This thesis is dedicated to my mother for instilling the importance of hard work and higher education. iii Contents Front Matter Contents ........................................................................................................ iv  List of Tables ................................................................................................. vi  List of Figures ............................................................................................. viii  List of Copyrighted Material ........................................................................ ix  List of Symbols ............................................................................................... x  1 Introduction 1  1.1  Background ............................................................................................ 1  1.2  Objective of the thesis ........................................................................... 4  1.3  Thesis outline ......................................................................................... 5  2 Literature Review 6  2.1  Scheduling Identical Parallel Machines with Single Resource ........... 6  2.2  Scheduling Identical Parallel Machines with Dual Resources .......... 14  3 Scheduling Identical Parallel Machines with Release Time Constraint using Single Resource 21  3.1  Introduction ......................................................................................... 21  3.2  Problem definition and mathematical model ..................................... 25  3.3  Tabu search algorithm ........................................................................ 28  3.3.1  Description of the basic TS algorithm ...................................... 28  3.3.2  Further intensification ............................................................. 36  3.4  Computational results ......................................................................... 37  3.4.1  Effect of varying release time on flow time ............................. 42  iv 3.5  Conclusion ............................................................................................ 50  4 Scheduling Identical Parallel Machines with Release Time Constraint using Dual Resources 51  4.1  Introduction ......................................................................................... 52  4.2  Problem description ............................................................................. 54  4.3  Solution approaches............................................................................. 56  4.3.1  Heuristics .................................................................................. 56  4.3.2  Tabu Search Heuristic (TSHu) Algorithm ............................... 59  4.3.3  Tabu search heuristic for dual resources (TSD) ...................... 59  4.4  Computational results ......................................................................... 60  4.5  Case study ............................................................................................ 69  4.6  Conclusion ............................................................................................ 72  5 Conclusion 73  5.1  Summary of research ........................................................................... 74  5.2  Future work ......................................................................................... 77  References .................................................................................................... 80  Appendix A: Identical Parallel Machines Scheduling with Release Time Constraint using Dual Resources ............................................................... 85  v List of Tables Table 1: Summary of previous works on identical parallel machines scheduling with single resource .................................................................................................................... 8  Table 2: Summary of literature review on parallel machines scheduling with dual resources ........................................................................................................................... 18  Table 3: Computational results for small problems .......................................................... 39  Table 4: Computational results for large problems ........................................................... 40  Table 5: Time required for TS algorithms and optimal solution ...................................... 41  Table 6: Results of TS+I with varying release time ......................................................... 44  Table 7: Comparison of TS + I & MFHA with varying release time ............................... 46  Table 8: Selected combinations ........................................................................................ 58  Table 9: Computational results of heuristics .................................................................... 61  Table 10: Comparison of two different arrival patterns .................................................... 62  Table 11: Computational results of all the solution approaches ....................................... 63  Table 12: Computational results of extended experiment ................................................ 65  Table 13: Time requirement of all solution approaches ................................................... 66  Table 14: Allocation of treatment chairs and nurses’ schedule ........................................ 70  Table 15: List of several combinations of heuristics ........................................................ 85  Table 16: Evaluation of Com1 & Com2 for values of α ................................................... 87  Table 17: Evaluation of Com3 & Com4 for values of α ................................................... 87  Table 18: Evaluation of Com5 & Com6 for values of α ................................................... 88  vi Table 19: Evaluation of Com7 & Com8 for values of α ................................................... 88  Table 20: Evaluation of Com9 & Com10 for values of α ................................................. 89  vii List of Figures Figure 1: A schematic representation of the correlation among release time, processing time, waiting time, completion time and flow time .......................................................... 23  Figure 2: A schematic representation of swap move ........................................................ 29  Figure 3: A schematic representation of insert move ....................................................... 30  Figure 4: Flow chart of basic TS algorithm ...................................................................... 33  Figure 5: Flow Chart of TS Algorithm with further intensification ................................. 35  Figure 6: Template obtained from TS+I ........................................................................... 48  Figure 7: An example of template obtained from TS+I using α=0.75 .............................. 49  Figure 8: An example of template obtained from heuristic .............................................. 67  Figure 9: An example of template obtained from TSD ................................................... 68  Figure 10: A scheduling template for patients in Chemotherapy treatment clinic ........... 71  viii List of Copyrighted Material Thesis of Ahmed Z., 2011, “Developing an Efficient Scheduling Template of a Chemo- therapy Treatment Unit: Simulation and Optimization Approach”, University of Manito- ba, Winnipeg, Manitoba, Canada. ix