TY - GEN
T1 - Single Bounded Parallel-Batch Machine Scheduling with an Unavailability Constraint and Job Delivery
AU - Fan, Jing
AU - Ng, C. T.
AU - Cheng, T. C.E.
AU - Shi, Hui
N1 - Funding Information:
Keywords: Parallel-batch · Production and delivery · Unavailability constraint · Approximation algorithm This research was supported in part by the National Natural Science Foundation of China (No.11601316). Fan was also supported in part by the key discipline “Applied Mathematics” of Shanghai Polytechnic University (No. XXKPY1604), Research Center of Resource Recycling Science and Engineering, and Gaoyuan Discipline of Shanghai − Environmental Science and Engineering (Resource Recycling Science and Engineering) of Shanghai Polytechnic University. Cheng was also supported in part by The Hong Kong Polytechnic University under the Fung Yiu King - Wing Hang Bank Endowed Professorship in Business Administration.
Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/8
Y1 - 2020/8
N2 - We consider a scheduling problem where a manufacturer processes a set of jobs for a customer and delivers the completed jobs to the customer. The job sizes and processing times are given. The objective is to minimize the maximum delivery time to the customer. In the production stage, one machine with an unavailability period is used to process the jobs. The machine has a fixed capacity and the jobs are processed in batches under the condition that the total size of the jobs in a batch cannot exceed the machine capacity. The processing time of a batch is the maximum processing time of the jobs contained in the batch. In addition, each batch is non-resumable, i.e., if the processing of a batch cannot be completed before the unavailability period, the batch needs to be processed anew after the unavailability interval. In the distribution stage, the manufacturer assigns a vehicle with a fixed capacity to deliver the completed jobs. The total size of the completed jobs in one delivery cannot exceed the vehicle capacity. We first consider the case where the jobs have the same size and arbitrary processing times, for which we provide a 3/2-approximation algorithm and show that the worst-case ratio is tight. We then consider the case where the jobs have the same processing time and arbitrary sizes, for which we provide a 5/3-approximation algorithm and show that the worst-case ratio is tight.
AB - We consider a scheduling problem where a manufacturer processes a set of jobs for a customer and delivers the completed jobs to the customer. The job sizes and processing times are given. The objective is to minimize the maximum delivery time to the customer. In the production stage, one machine with an unavailability period is used to process the jobs. The machine has a fixed capacity and the jobs are processed in batches under the condition that the total size of the jobs in a batch cannot exceed the machine capacity. The processing time of a batch is the maximum processing time of the jobs contained in the batch. In addition, each batch is non-resumable, i.e., if the processing of a batch cannot be completed before the unavailability period, the batch needs to be processed anew after the unavailability interval. In the distribution stage, the manufacturer assigns a vehicle with a fixed capacity to deliver the completed jobs. The total size of the completed jobs in one delivery cannot exceed the vehicle capacity. We first consider the case where the jobs have the same size and arbitrary processing times, for which we provide a 3/2-approximation algorithm and show that the worst-case ratio is tight. We then consider the case where the jobs have the same processing time and arbitrary sizes, for which we provide a 5/3-approximation algorithm and show that the worst-case ratio is tight.
KW - Approximation algorithm
KW - Parallel-batch
KW - Production and delivery
KW - Unavailability constraint
UR - http://www.scopus.com/inward/record.url?scp=85089716413&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-57602-8_47
DO - 10.1007/978-3-030-57602-8_47
M3 - Conference article published in proceeding or book
AN - SCOPUS:85089716413
SN - 9783030576011
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 525
EP - 536
BT - Algorithmic Aspects in Information and Management - 14th International Conference, AAIM 2020, Proceedings
A2 - Zhang, Zhao
A2 - Li, Wei
A2 - Du, Ding-Zhu
PB - Springer
T2 - 14th International Conference on Algorithmic Aspects in Information and Management, AAIM 2020
Y2 - 10 August 2020 through 12 August 2020
ER -