Unary NP-hardness of transportation and batching scheduling to minimize the total weighted completion time

被引：0

作者：

Wei, Hongjun ^{[1
]}

Gao, Yuan ^{[1
]}

Yuan, Jinjiang ^{[1
]}

机构：

[1] Zhengzhou Univ, Sch Math & Stat, Zhengzhou 45000, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2025年 / 369卷

基金：

中国国家自然科学基金;

关键词：

Transportation; Batching scheduling; Unary NP-hard; The total weighted completion time; COORDINATION; MACHINE;

D O I：

10.1016/j.dam.2025.02.023

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, we study the coordination of transportation and batching scheduling with one single vehicle to minimize the total weighted completion time. When the batch capacity is 2, the computational complexity of this problem has been reported open in the literature. We show in this paper that the problem is unary NP-hard. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

引用

页码：45 / 52

页数：8

共 8 条

[1] The third comprehensive survey on scheduling problems with setup times/costs [J].

Allahverdi, Ali .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 246 (02) :345-378

[2] Speeding up a Rollout algorithm for complex parallel machine scheduling [J].

Ciavotta, Michele ;

Meloni, Carlo ;

Pranzo, Marco .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2016, 54 (16) :4993-5009

[3]

Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness

[4]

Graham R. L., 1979, Discrete Optimisation, P287

[5] The coordination of transportation and batching scheduling [J].

Tang, Lixin ;

Gong, Hua .

APPLIED MATHEMATICAL MODELLING, 2009, 33 (10) :3854-3862

[6] Transportation and Batching Scheduling for Minimizing Total Weighted Completion Time [J].

Wei, Hongjun ;

Yuan, Jinjiang ;

Gao, Yuan .

MATHEMATICS, 2019, 7 (09)

[7] Two-machine flow-shop scheduling with equal processing time on the second machine for minimizing total weighted completion time [J].

Wei, Hongjun ;

Yuan, Jinjiang .

OPERATIONS RESEARCH LETTERS, 2019, 47 (01) :41-46

[8] New results on the coordination of transportation and batching scheduling [J].

Zhu, Hongli ;

Leus, Roel ;

Zhou, Hong .

APPLIED MATHEMATICAL MODELLING, 2016, 40 (5-6) :4016-4022

← 1 →