No-wait scheduling problem refers to the set of problems in which a number of jobs are available for processing on a number of machines with the added constraint that there should be no waiting time between consecutive operations of the jobs. It is well-known that most of the no-wait scheduling problems are strongly NP-hard. Moreover, no-wait scheduling problems have numerous real-life applications. This thesis studies a wide range of no-wait scheduling problems, along with side constraints that make such problems more applicable. First, 2-machine no-wait flow shop problem is studied. Afterwards, setup times and single server constraints are added to this problem in order to make it more applicable. Then, job shop version of this problem is further researched. Analytical results for both of these problems are presented; moreover, efficient algorithms are developed and applied to large instances of these problems.
Afterward, general no-wait flow shop problem (NWFS) is the focus of the thesis. First, the NWFS is studied; mathematical models as well as metaheuristics are developed for NWFS. Then, setup times are added to NWFS in order to make the problem more applicable. Finally, the case of sequence dependent setup times is further researched. Efficient algorithms are developed for both problems.
Finally, no-wait job shop (NWJS) problem is studied. Literature has proposed different methods to solve NWJS; the most successful approaches decompose the problem into a timetabling sub-problem and a sequencing sub-problem. Different sequencing and timetabling algorithms are developed to solve NWJS.
This thesis provides insight to several no-wait scheduling problems. A number of theorems are discussed and proved in order to find the optimum solution of no-wait problems with special characteristics. For the problems without such characteristics, mathematical models are developed. Metaheuristics are utilized to deal with large-instances of NP-hard problems. Computational results show that the developed methods in this thesis are very effective and efficient compared to the competitive methods available in the literature.
Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:MWU.1993/21709 |
Date | January 2013 |
Creators | Samarghandi, Hamed |
Contributors | ElMekkawy, Tarek (Mechanical and Manufacturing Engineering), Luo, Yunhua (Mechanical and Manufacturing Engineering) Filizadeh, Shaahin (Electronic and Computer Engineering) Zolfaghari, Saeed (Ryerson University) |
Publisher | International Journal of Industrial Engineering, International Journal of Production Research, The International Journal of Advanced Manufacturing Technology, The International Journal of Advanced Manufacturing Technology |
Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
Detected Language | English |
Page generated in 0.0025 seconds