Exact and approximate solution methods for batch scheduling problems

批量调度问题的精确和近似求解方法

• 批准号: RGPIN-2019-05691
• 负责人: Ozturk, Onur
• 金额: $ 1.89万
• 依托单位: University of Ottawa
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=738454
• 关键词: Exact; approximate; solution; methods; batch

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.

在生产和服务行业中，活动的调度和排序对于任务资源的效率起着至关重要的作用。批调度是一种将多个作业分组并一起处理的调度分配类型。半导体制造、家具制造、化工生产、金属工业、纺织工业、交通运输等。相对于加拿大经济来说，遇到批量调度的两个非常重要的行业是钢铁和铝生产，2017年这些行业的就业人数较多。比总共33,000 人，为加拿大的国内生产总值贡献了约 90 亿美元 生产计划的决策是一个动态过程，不可能使用分析模型来确定一般（每日、每周等）政策的应用。大多数时候，这些模型仅有助于解决小规模问题，因为它们的数学复杂性是为包含尽可能多的模型的通用模型开发有效的解决方法。的关键现实方面虽然批量调度文献中有丰富的启发式和元启发式求解方法，但针对一些具有简化假设的问题，大多数现有工作都开发了数学分解方法和精确算法。所提出的研究计划旨在通过对现实生活中的假设（例如并行机器、工作发布日期、截止日期、工作类别、工作维度等进行分组）来开发新颖的解决方案技术。首先，我们将重点关注数学分解。方法基于能够表示现实生活假设的时间索引列生成模型（还根据问题类型加上行生成）然后我们将继续使用另一种设置，其中问题数据无法提前完全了解。将开发在线近似算法来做出实时配料决策。测试优化配料步骤如何影响整个系统的效率也至关重要。为此，我们将为钢铁生产建立通用模拟模型，并集成之前开发的模型。在该模拟中将批处理算法作为调度决策拟议的研究主要针对运筹学（OR）界，但它也旨在让从业者在生产计划和调度方面做出最佳决策，我也期望这项研究的结果能够为运筹学界产生新的研究思路。有助于提高在生产行业中应用 OR 技术的理念。