Hybrid constraint generation approaches for industrial scheduling and logistics

工业调度和物流的混合约束生成方法

• 批准号: 517947-2017
• 负责人: Beck, Chris
• 金额: $ 1.56万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Collaborative Research and Development Grants
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=697038
• 关键词: Hybrid; constraint; generation; approaches; industrial

The transportation of goods (i.e., logistics) and the scheduling of manufacturing processes form two key elements in the Canadian economy. In practice, and in the research literature, Operations Research techniques, such as mixed integer programming, constraint programming, and heuristics, are applied to such problems. Over the past 15 years, the PI has contributed to the research and development of hybrid constraint generation approaches to hard combinatorial problems, including logistics and scheduling. Such techniques rely on a problem decomposition and the exchange of constraints amongst the sub-problems to ensure that optimal solutions or solution quality guarantees can be found. Evidence in the literature points to such techniques often achieving one or two orders-of-magnitude increase in problem solving power compared to traditional approaches. This project will further develop hybrid constraint generation techniques for four logistics and scheduling problems that are currently solved by traditional approaches by the industrial partner, Visual Thinking International Ltd: Great Lakes Inventory Routing, Sequencing for Plating Lines, Coil Trim Optimization, and Batch Optimization. These are real-world versions of core problems that are relevant to many manufacturing and logistics companies and have been studied in the literature, but for which no constraint generation techniques have been developed. The project will (1) transfer the technology that the PI has been part of developing in the academic literature to a Canadian software company and (2) further develop the constraint generation approach through the challenge of addressing the industrial-scale problems via data from the industrial partner.

货物运输(即物流)和制造过程的调度构成了加拿大经济中的两个关键要素。在实践中，以及在研究文献中，运筹学的技术，如混合整数规划、约束规划和启发式，都被应用于这样的问题。在过去的15年里，PI为混合约束生成方法的研究和开发做出了贡献，这些方法适用于包括物流和调度在内的复杂组合问题。这种技术依赖于问题分解和子问题之间的约束交换，以确保能够找到最优解或解的质量保证。文献中的证据表明，与传统方法相比，这种技术通常能在解决问题的能力上实现一到两个数量级的提高。 该项目将进一步为四个物流和调度问题开发混合约束生成技术，这些问题目前由工业合作伙伴视觉思维国际有限公司通过传统方法解决：五大湖库存路线、电镀生产线排序、线圈修剪优化和批量优化。这些是与许多制造和物流公司相关的核心问题的真实世界版本，已经在文献中进行了研究，但还没有为这些问题开发出约束生成技术。 该项目将(1)将PI在学术文献中开发的技术转移到一家加拿大软件公司，以及(2)通过来自工业合作伙伴的数据解决工业规模问题的挑战，进一步开发约束生成方法。