Serial-batching scheduling problem to minimize total weighted completion time

被引：0
|
作者：
Tian, Le [1 ]
Zhao, Chuan-Li [1 ]
机构：
[1] Coll. of Mathematics and Systems Science, Shenyang Normal Univ., Shenyang 110034, China
来源：
Xi Tong Gong Cheng Yu Dian Zi Ji Shu/Systems Engineering and Electronics | 2007年 / 29卷 / 11期
关键词：
Computational complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The serial-batching scheduling problem on parallel machines is considered to minimize total weight completion time with the restriction that each batch contains exactly k jobs and the processing time is equal to the sum of the processing times of all the jobs in a batch. For parallel machines, the problem is strongly NP-hard. A algorithm is given for the following two special case of this problem: (1) Ail the jobs have the same weight; (2) All the jobs have the same processing time. The running time of the proposed algorithm is analyzed, at the same time, a numerical example is given.
引用
收藏
页码：1883 / 1885
相关论文
共 50 条
  • [1] Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time
    Yuan, J. J.
    Lin, Y. X.
    Cheng, T. C. E.
    Ng, C. T.
    INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, 2007, 105 (02) : 402 - 406
  • [2] Open shop scheduling problem to minimize total weighted completion time
    Bai, Danyu
    Zhang, Zhihai
    Zhang, Qiang
    Tang, Mengqian
    ENGINEERING OPTIMIZATION, 2017, 49 (01) : 98 - 112
  • [3] Unary NP-hardness of transportation and batching scheduling to minimize the total weighted completion time
    Wei, Hongjun
    Gao, Yuan
    Yuan, Jinjiang
    DISCRETE APPLIED MATHEMATICS, 2025, 369 : 45 - 52
  • [4] Serial-batching scheduling with two agents to minimize makespan and maximum cost
    He, Cheng
    Xu, Chunqi
    Lin, Hao
    JOURNAL OF SCHEDULING, 2020, 23 (05) : 609 - 617
  • [5] Serial-batching scheduling with two agents to minimize makespan and maximum cost
    Cheng He
    Chunqi Xu
    Hao Lin
    Journal of Scheduling, 2020, 23 : 609 - 617
  • [6] Transportation and Batching Scheduling for Minimizing Total Weighted Completion Time
    Wei, Hongjun
    Yuan, Jinjiang
    Gao, Yuan
    MATHEMATICS, 2019, 7 (09)
  • [7] Parallel-machine batching and scheduling to minimize total completion time
    Cheng, TCE
    Chen, ZL
    Kovalyov, MY
    Lin, BMT
    IIE TRANSACTIONS, 1996, 28 (11) : 953 - 956
  • [8] Parallel-machine batching and scheduling to minimize total completion time
    The Hong Kong Polytechnic Univ, Kowloon, Hong Kong
    IIE Trans, 11 (953-956):
  • [9] Scheduling with Rejection to Minimize the Total Weighted Completion Time
    Zhang, Shu-Xia
    Cao, Zhi-Gang
    Zhang, Yu-Zhong
    OPERATIONS RESEARCH AND ITS APPLICATIONS, PROCEEDINGS, 2009, 10 : 111 - +
  • [10] On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times
    Ng, CT
    Cheng, TCE
    Yuan, JJ
    Liu, ZH
    OPERATIONS RESEARCH LETTERS, 2003, 31 (04) : 323 - 326
12345