Exact and approximate solution methods for batch scheduling problems

在生产和服务行业中，作业的调度和排序在有效地将任务分配给资源方面起着至关重要的作用。批处理调度是将多个作业分组并一起处理的调度类型。遇到批处理调度的一些例子是半导体制造、家具制造、化工生产、金属工业、纺织工业、交通运输等。相对于加拿大经济，遇到批处理调度的两个非常重要的行业是钢铁和铝生产。2017年，这些行业共雇用超过3.3万人，为加拿大国内生产总值贡献了约90亿美元。生产计划决策是一个动态的过程，一般(每天、每周等)的应用。政策不太可能确定。分析模型可用于做出最优(或接近最优)的分批决策。在大多数情况下，由于这些模型的数学复杂性，它们只能帮助解决小规模问题。我们的目标是为一个通用模型开发有效的解决方法，该模型尽可能多地结合批处理调度问题的更关键的现实方面。虽然批处理调度文献中有丰富的启发式和元启发式求解方法，但在简化假设的情况下，针对少数问题提出了数学分解方法和精确算法。关于近似算法，现有的大部分工作都集中在最大完工时间最小化问题上。所提出的研究计划旨在通过将诸如并行机、作业发布日期、交货期、作业族、作业维度等真实生活假设分组来开发新的解决方案技术。首先，我们将专注于基于能够表示真实生活假设的时间索引列生成模型(也结合行生成，取决于问题类型)的数学分解方法。然后，我们将继续进行另一种设置，在该设置中，问题数据事先并不完全知道。在这种情况下，我们将开发在线近似算法来进行实时批处理决策。测试优化批处理步骤如何影响整个系统的效率也是至关重要的。为此，我们将为钢铁生产建立一个通用的模拟模型，并将以前开发的分批算法作为调度决策集成到该模拟模型中。拟议的研究主要针对运筹学(OR)社区，但它也打算让实践者在生产计划和调度中做出最佳决策。我也期待这项研究的结果为OR社区产生新的研究思路，并帮助改进在生产行业中应用OR技术的概念。

In production and service industries, the scheduling and sequencing of activities play a crucial role in the efficient allocation of tasks to resources. Batch scheduling is the type of scheduling in which multiple jobs are grouped and processed together. Some examples where batch scheduling is encountered are semiconductor manufacturing, furniture manufacturing, chemical production, metal industry, textile industry, transportation, etc. Vis-à-vis the Canadian economy, two very important sectors where batch scheduling is encountered are steel and aluminum production. In 2017, these industries employed more than a total of 33,000 people and contributed around $9 billion to Canada's gross domestic product. Decision making in production planning is a dynamic process and the application of a general (daily, weekly, etc.) policy is unlikely to be determined. Analytical models can be used to take optimal (or close to optimal) batching decisions. Most of the time, these models are helpful to solve only small size problems because of their mathematical complexity. Our aim is to develop efficient solution methods for a generic model that incorporates as many of the more crucial realistic aspects of the batch scheduling problem as we can. While the batch scheduling literature is rich in heuristic and metaheuristic solution methods, mathematical decomposition methods and exact algorithms are developed for a few problems with simplified hypotheses. With regards to approximation algorithms, most of the existing work has focused on makespan minimization. The proposed research program seeks to develop novel solution techniques by grouping real-life hypotheses such as parallel machines, job release dates, due dates, job families, job dimensions, etc. At first, we will focus on mathematical decomposition methods based on time indexed column generation models (also coupled with row generation depending on the problem type) capable of representing real-life hypotheses. Then we will continue with another setting in which problem data is not fully known in advance. For that setting, we will develop online approximation algorithms to take real-time batching decisions. It is also crucial to test how optimizing the batching step effects the efficiency of the overall system. For that purpose, we will build a generic simulation model for steel production and integrate previously developed batching algorithms as scheduling decisions in that simulation model. The proposed research targets primarily the Operations Research (OR) community, but it also intends to allow practitioners to take optimum decisions in production planning and scheduling. I also expect the outcome of this research to generate new research ideas for the OR community and help to improve the notion of applying OR techniques in production industries.