清晨好,您是今天最早来到科研通的研友!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您科研之路漫漫前行!

An Exact Branch-Price-and-Cut Algorithm for the Unrelated Parallel Machine Scheduling Problem

计算机科学 调度(生产过程) 作业车间调度 算法 地铁列车时刻表 动态优先级调度 流水车间调度 数学优化 公平份额计划 分界 单调速率调度 单机调度 软件 并行计算 有向无环图 近似算法 作业调度程序 最小空闲时间调度 计算复杂性理论 处理器调度 两级调度
作者
Yu Yang,Xiaolong Li,Roberto Baldacci,Zhiqiao Wu,Wei Sun,唐加福,Han Zhu
出处
期刊:Informs Journal on Computing [Institute for Operations Research and the Management Sciences]
被引量:2
标识
DOI:10.1287/ijoc.2024.0704
摘要

We investigate the Unrelated Parallel Machine Scheduling Problem (UPMSP), where independent jobs need scheduling on unrelated parallel machines. Each job has a distinct processing time, a weight, and a completion time. The goal is to find an optimal schedule that minimizes the total weighted completion time. This problem has been extensively studied in the scheduling literature. To address the UPMSP, we model feasible schedules using Smith’s rule, representing them as paths on directed acyclic graphs, and derive a corresponding set-partitioning-based model. To solve the model, we introduce a branch-price-and-cut (BPC) algorithm with dynamic shrink upper bounds, incorporating state-of-the-art techniques such as the bucket graph-based labeling algorithm, limited-memory subset-row cuts, and strong branching. Notably, the proposed BPC algorithm is the first exact algorithm capable of addressing widespread real-life UPMSPs with rational-number processing times. Extensive numerical experiments demonstrate that our proposed algorithm outperforms state-of-the-art algorithms for the UPMSP with integer-valued processing times, solving larger-scale instances with up to 20 machines and 200 jobs efficiently. Furthermore, it effectively addresses real-life instances (from JD.com) with rational-number processing times involving up to 20 machines and 200 jobs. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: Financial support from the National Natural Science Foundation of China [Grants 72571039, 72322018, 72272027, 72471050, and 72171043] and the Fundamental Research Funds for the Central Universities [Grant DUT23RC(3)070] is gratefully acknowledged. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0704 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0704 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
小巧的绮完成签到,获得积分10
1秒前
越过山丘完成签到,获得积分10
1秒前
null的应助被369ninja采纳,获得10
2秒前
求助完成签到,获得积分10
3秒前
幸福的盼芙完成签到,获得积分10
3秒前
独特的又菱完成签到,获得积分10
4秒前
ryyy1208完成签到,获得积分10
4秒前
ybcy完成签到,获得积分10
5秒前
wrxaa完成签到,获得积分10
6秒前
8秒前
大力的映天完成签到,获得积分10
9秒前
潘润朗完成签到,获得积分10
9秒前
qimoqi完成签到,获得积分10
10秒前
ln完成签到,获得积分10
10秒前
莫忘初心完成签到,获得积分10
10秒前
11秒前
11秒前
搜集达人的应助被TingtingGZ采纳,获得10
13秒前
友好语风完成签到,获得积分10
15秒前
NiaoJiang完成签到,获得积分10
15秒前
Wtony完成签到 ,获得积分0
15秒前
INC完成签到,获得积分10
17秒前
迷人的危险最值钱完成签到,获得积分10
19秒前
美好的初翠完成签到,获得积分10
20秒前
July完成签到,获得积分10
20秒前
kkdg完成签到,获得积分10
22秒前
邓大瓜完成签到,获得积分10
22秒前
脑洞疼的应助被369ninja采纳,获得10
22秒前
MaidLingYan完成签到,获得积分10
26秒前
26秒前
26秒前
DrPika完成签到,获得积分10
26秒前
KKDG完成签到,获得积分10
27秒前
熊熊熊完成签到,获得积分10
27秒前
27秒前
ZHZ完成签到,获得积分10
28秒前
29秒前
聪明的羿完成签到,获得积分10
30秒前
joker000717完成签到,获得积分10
31秒前
TingtingGZ发布了新的文献求助10
31秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
八旗制度の研究 600
plantTFDB 508
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8173194
求助须知:如何正确求助?哪些是违规求助? 9565558
关于积分的说明 21780496
捐赠科研通 7767299
什么是DOI,文献DOI怎么找? 3431542
关于科研通互助平台的介绍 2555697
邀请新用户注册赠送积分活动 2476688