Single machine lot scheduling to minimize the total weighted (discounted) completion time

被引：16
作者：
Zhang, E. [1 ]
Liu, Ming [2 ]
Zheng, Feifeng [3 ]
Xu, Yinfeng [3 ]
机构：
[1] Shanghai Univ Finance & Econ, Sch Informat Management & Engn, Shanghai 200433, Peoples R China
[2] Tongji Univ, Sch Econ & Management, Shanghai 200092, Peoples R China
[3] Donghua Univ, Glorious Sun Sch Business & Management, Shanghai 200051, Peoples R China
来源：
INFORMATION PROCESSING LETTERS | 2019年 / 142卷
基金：
中国国家自然科学基金;
关键词：
Algorithms; Lot scheduling; Single machine; WSPT rule; FLOW-TIME; COMMON;
D O I：
10.1016/j.ipl.2018.10.002
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this work, we investigate the problem of single machine lot scheduling where each lot contains one or more jobs and is of identical processing time. Jobs with different sizes are splittable and shall be processed in consecutive lots. Any completed (part of a) job is delivered to the customer on its completion. We prove that the WSPT (Weighted Shortest Processing Time first) rule is optimal for both models of minimizing total weighted completion time and minimizing total weighted discounted completion time. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码：46 / 51
页数：6
相关论文
共 14 条
[1]   Single batch machine scheduling with deliveries [J].
Cheng, B. -Y. ;
Leung, J. Y. -T. ;
Li, K. ;
Yang, S. -L. .
NAVAL RESEARCH LOGISTICS, 2015, 62 (06) :470-482
[2]   Lot scheduling on a single machine [J].
Hou, Yung-Tsung ;
Yang, Dar-Li ;
Kuo, Wen-Hung .
INFORMATION PROCESSING LETTERS, 2014, 114 (12) :718-722
[3]   Minimizing flow-time on a single machine with integer batch sizes [J].
Mosheiov, G ;
Oron, D ;
Ritov, Y .
OPERATIONS RESEARCH LETTERS, 2005, 33 (05) :497-501
[4]   ONE-PASS BATCHING ALGORITHMS FOR THE ONE-MACHINE PROBLEM [J].
NADDEF, D ;
SANTOS, C .
DISCRETE APPLIED MATHEMATICS, 1988, 21 (02) :133-145
[5]  
Pinedo M., 2002, SCHEDULING THEORY AL
[6]   BATCHING IN SINGLE OPERATION MANUFACTURING SYSTEMS [J].
SANTOS, C ;
MAGAZINE, M .
OPERATIONS RESEARCH LETTERS, 1985, 4 (03) :99-103
[7]   A POLYNOMIAL ALGORITHM FOR A ONE MACHINE BATCHING PROBLEM [J].
SHALLCROSS, DF .
OPERATIONS RESEARCH LETTERS, 1992, 11 (04) :213-218
[8]   A note on a single-machine lot scheduling problem with indivisible orders [J].
Yang, Dar-Li ;
Hou, Yung-Tsung ;
Kuo, Wen-Hung .
COMPUTERS & OPERATIONS RESEARCH, 2017, 79 :34-38
[9]   A single-machine scheduling problem with learning effects in intermittent batch production [J].
Yang, Dar-Li ;
Kuo, Wen-Hung .
COMPUTERS & INDUSTRIAL ENGINEERING, 2009, 57 (03) :762-765
[10]   Improved Algorithms for Single-Machine Serial-Batch Scheduling With Rejection to Minimize Total Completion Time and Total Rejection Cost [J].
Yin, Yunqiang ;
Cheng, Tai Chiu Edwin ;
Wang, Dujuan ;
Wu, Chin-Chia .
IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS, 2016, 46 (11) :1578-1588
12