Grants and Contributions:

Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023)

The objective of this proposal is to further advance my research program in the realm of the no-wait and time-lag scheduling optimization. No-wait constraints denote that there should be no waiting time between consecutive operations of a job, which is a fundamental assumption in certain environments. Scheduling problems with time-lag constraints are a generalization of their no-wait version. Time-lag constraints force the jobs or the operations of the jobs to start or finish within a certain time window after the previous jobs or operations are completed. No-wait and time-lag constraints model situations in which a long delay between the starting time of an operation and the finish time of the previous operations is discouraged because it may damage or deteriorate the product.

For example, in the food industry, many of the production procedures involve perishable products, i.e., once the food is prepared and cooked, it must undergo the chilling process before a certain amount of time is elapsed or it must be discarded. Similar constraints are in place in industries in which the risk of product contamination must be reduced. One can list biotechnology industries, for example, blood transfusion as such fields. Automated medical laboratories usually use a combination of minimal and maximal time-lags to schedule the chemical reactions correctly. Hall and Sriskandarajah [16] and Deppner [17] provide a comprehensive review of the applications of the problem.

The proper objective functions to consider include minimizing the cost of production or the total processing time of the contracts in a factory; reducing the waiting time of the patients in a healthcare setting or clients in a government office. Another possibility is maximizing the utilization of the available resources. The mentioned problems are NP-hard. My research in this area during the past few years reveals that to solve the no-wait or time-lag scheduling problems to optimality using mathematical programming models, the problem instance should have less than 20 jobs.

The proposed solution methods in this application progress the available literature by applying novel approaches to the scheduling problems that I have been studying for the past eight years. These methods include finding tight upper- or lower bounds for the optimal solution using semidefinite programming or Lagrangian relaxation; using decomposition techniques such as Bender’s method; and conducting stochastic optimization techniques to the non-deterministic cases.

The mentioned problems and solution methods are sophisticated yet fundamental and fill the gaps that currently exist in the literature. Moreover, the practicality of the defined problems and the solution methods will lead to the efficiency improvement and optimization of the Canadian and international businesses.