Scheduling Optimization of Manufacturing and Service Environments with Time-Lag Constraints

这项建议的目的是为了进一步推进我在无等待和时滞调度优化领域的研究计划。无等待约束表示作业的连续操作之间不应该有等待时间，这在某些环境中是一个基本假设。带时滞约束的调度问题是其无等待模型的推广。时间延迟约束迫使作业或作业的操作在先前的作业或操作完成后的特定时间窗口内开始或完成。无等待和时滞约束是指不鼓励在工序开始时间和前一道工序的结束时间之间出现长时间延迟的情况，因为这可能会损坏或恶化产品。举例来说，在食品行业，很多生产工序都涉及易腐烂的产品，即食物一旦烹调好后，便要经过冷藏过程，才会经过一段时间，否则便须弃置。在必须降低产品污染风险的行业，也存在类似的限制。人们可以将生物技术行业列为这样的领域，例如输血。自动化医学实验室通常使用最小和最大时间延迟的组合来正确地安排化学反应。Hall和Sriskandarajah[16]和Deppner[17]对问题的应用进行了全面的回顾。要考虑的适当目标函数包括最小化生产成本或工厂合同的总处理时间；减少病人在医疗保健环境中的等待时间或客户在政府办公室的等待时间。另一种可能性是最大限度地利用现有资源。上述问题是NP-Hard问题。我过去几年在这方面的研究表明，要用数学规划模型解决无等待或时滞调度问题的最优问题，问题实例的作业数应少于20个。本申请中提出的解决方法通过应用新的方法来解决我过去八年来一直研究的调度问题，从而改进了现有的文献。这些方法包括使用半定规划或拉格朗日松弛法找到最优解的紧致上下界；使用分解技术(如Bender方法)；以及对不确定情况进行随机优化技术。提到的问题和解决方法是复杂而基本的，填补了目前文献中存在的空白。此外，定义的问题和解决方法的实用性将导致加拿大和国际企业效率的提高和优化。

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.