A computational study of practical issues arising in short-term scheduling of a multipurpose facility

scheduling;nonuniform discretizations;dynamic timepoints;rescheduling

Stevenson, Zachariahadvisor:Fukasawa, Ricardo ; advisor:Ricardez-Sandoval, Luis ; affiliation1:Faculty of Mathematics ; Fukasawa, Ricardo ; Ricardez-Sandoval, Luis ;

University of Waterloo

关键词: Master Thesis;    rescheduling;    dynamic timepoints;    scheduling;    nonuniform discretizations;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/14404/1/Stevenson_Zachariah.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

This thesis focuses on two important considerations when solving short term scheduling problems for multipurpose facilities: deciding when rescheduling should be performed and choosing efficient time representations for the scheduling problems. This class of scheduling problems is of practical importance as it may be used for scheduling chemical production facilities, flexible manufacturing systems, and analytical services facilities, among others. In these cases, improving the efficiency of scheduling operations may lead to increased yield, or reduced makespan, resulting in greater profits or customer satisfaction. Therefore, efficiently solving these problems is of great practical interest. One aspect of real world implementations of these problems is the presence of uncertainty, such as in the form of new jobs arriving, or a machine breaking down. In these cases, one may want or need to reschedule operations subject to the new disturbance. An investigation into how often to perform these reschedulings is addressed in the first part of the thesis. When formulating these problems, one must also choose a time representation for executing scheduling operations over. A dynamic approach is proposed in the second part of the thesis which we show can potentially yield substantial computational savings when scheduling over large instances.The first part of this thesis addresses the question of when to reschedule operations for a facility that receives new jobs on a daily basis. Through computational experiments that vary plant parameters, such as the load and the capacity of a facility, we investigate the effects these parameters have on plant performance under periodic rescheduling. These experiments are carried out using real data from an industrial-scale facility. The results show that choosing a suitable rescheduling policy depends on some key plant parameters. In particular, by modifying various parameters of the facility, the performance ranking of the various rescheduling policies may be reversed compared to the results obtained with nominal parameter values. This highlights the need to consider both facility characteristics and what the crucial objective of the facility is when selecting a rescheduling policy.The second part of this thesis deals with the issue of deciding which timepoints to include in our model formulations. In general, adding more timepoints to the model will offer more flexibility to the solver and hence result in more accurate schedules. However, these extra timepoints will also increase the size of the model and accordingly the computational cost of solving the model. We propose an iterative framework to refine an initial coarse uniform discretization, by adding key timepoints that may be most beneficial, and removing timepoints which are unnecessary from the model. This framework is compared against existing static discretizations using computational experiments on an analytical services facility. The results of these experiments demonstrate that when problems are sufficiently large, our proposed dynamic method is able to achieve a better tradeoff between objective value and CPU time than the currently used discretizations in the literature.