An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines

Xiong Xiaoyun; Zhou Peng; Yin Yunqiang; Cheng T. C. E.; Li Dengfeng

首页> 外文期刊>Naval Research Logistics >An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines

【24h】

An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines

机译：无关并行机上用于多任务调度的精确分支价格算法

获取原文

获取原文并翻译 | 示例

获取外文期刊封面封底 >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

We consider the multitasking scheduling problem on unrelated parallel machines to minimize the total weighted completion time. In this problem, each machine processes a set of jobs, while the processing of a selected job on a machine may be interrupted by other available jobs scheduled on the same machine but unfinished. To solve this problem, we propose an exact branch-and-price algorithm, where the master problem at each search node is solved by a novel column generation scheme, called in-out column generation, to maintain the stability of the dual variables. We use a greedy heuristic to obtain a set of initial columns to start the in-out column generation, and a hybrid strategy combining a genetic algorithm and an exact dynamic programming algorithm to solve the pricing subproblems approximately and exactly, respectively. Using randomly generated data, we conduct numerical studies to evaluate the performance of the proposed solution approach. We also examine the effects of multitasking on the scheduling outcomes, with which the decision maker can justify making investments to adopt or avoid multitasking.

机译：我们考虑不相关并行机上的多任务调度问题，以最大程度地减少总加权完成时间。在此问题中，每台机器都处理一组作业，而在一台机器上对选定作业的处理可能会被同一台机器上计划但未完成的其他可用作业打断。为了解决这个问题，我们提出了一种精确的分支价格算法，其中每个搜索节点的主问题都通过一种新颖的列生成方案（称为进出列生成）来解决，以保持对偶变量的稳定性。我们使用贪婪的启发式方法来获取一组初始列，以开始进出列的生成，并使用混合策略结合遗传算法和精确动态规划算法来分别近似和精确地解决定价子问题。使用随机生成的数据，我们进行了数值研究，以评估提出的解决方案方法的性能。我们还研究了多任务处理对计划结果的影响，决策者可以以此来证明进行或采用多任务处理的投资是合理的。

著录项

来源
《Naval Research Logistics》 |2019年第6期|502-516|共15页
作者
Xiong Xiaoyun; Zhou Peng; Yin Yunqiang; Cheng T. C. E.; Li Dengfeng;
展开▼
作者单位

China Univ Petr, Sch Econ & Management, Qingdao, Shandong, Peoples R China;

China Univ Petr, Sch Econ & Management, Qingdao, Shandong, Peoples R China;

Univ Elect Sci & Technol China, Sch Management & Econ, Chengdu 610054, Sichuan, Peoples R China;

Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Kowloon, Hong Kong, Peoples R China;

Univ Elect Sci & Technol China, Sch Management & Econ, Chengdu 610054, Sichuan, Peoples R China;

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类
关键词
branch-and-price; column generation; multitasking; scheduling;

机译：分支价格;柱生成;多任务;调度;

相似文献

外文文献
中文文献
专利

1. An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines [J] . Xiong Xiaoyun, Zhou Peng, Yin Yunqiang, Naval Research Logistics . 2019,第6期

机译：在无关的并联机器上的多任务调度的精确分支和价格算法
2. Using high performance computing for unrelated parallel machine scheduling with sequence-dependent setup times: Development and computational evaluation of a parallel branch-and-price algorithm [J] . Rauchecker Gerhard, Schryen Guido Computers & operations research . 2019,第APRa期

机译：将高性能计算用于与序列相关的建立时间的无关并行机器调度：并行分支价格算法的开发和计算评估
3. Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times [J] . Pedro Leite Rocha, Martin Gomez Ravetti, Geraldo Robson Mateus, Computers & operations research . 2008,第4期

机译：具有不相关并行机器以及与序列和机器相关的建立时间的调度问题的精确算法
4. Heuristic and Meta-heuristic Algorithms for the Online Scheduling on Unrelated Parallel Machines with Machine Eligibility Constraints [C] . Shuang Cai, Qifeng Xun, Ke Liu, International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery . 2018

机译：具有机器资格约束的无关并行机在线调度的启发式和元启发式算法
5. Unrelated parallel machine scheduling with sequence-dependent setup times and machine eligibility restrictions for minimizing the makespan. [D] . Salem, Ameer Hassan. 1999

机译：无关的并行机器调度，具有与序列有关的设置时间和机器合格限制，可最大程度地缩短制造周期。
6. MIP Models and Hybrid Algorithms for Simultaneous Job Splitting and Scheduling on Unrelated Parallel Machines [O] . Duygu Yilmaz Eroglu, H. Cenk Ozmutlu -1

机译：在无关并行机上同时进行作业分割和调度的MIP模型和混合算法
7. A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching [O] . Kowalczyk Daniel, Leus Roel 2016

机译：一种使用ZDD和通用分支进行并行机器调度的分支价格算法

An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines

摘要

著录项

相似文献

相关主题

期刊订阅