Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery
- PDF / 435,404 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 169 Views
Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery Ru-Bing Chen1 · Ling-Fa Lu1 · Jin-Jiang Yuan1 · Li-Qi Zhang2
Received: 6 September 2017 / Revised: 17 January 2018 / Accepted: 8 June 2018 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2018
Abstract This paper considers the integrated production and delivery scheduling on a serial batch machine, in which split is allowed in the delivery of the jobs. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. Lu et al. (Theor Comput Sci 572:50–57, 2015) showed that this problem is strongly NP-hard, and presented a 23 -approximation algorithm. In this paper, we present an improved 43 -approximation algorithm for this problem. We also present a polynomial-time algorithm for the special case when all jobs have the identical weight. Keywords Scheduling · Production and delivery · Serial batch · Approximation algorithm Mathematics Subject Classification 90B35
This research was supported by the National Natural Science Foundation of China (Nos. 11271338, 11771406, 11571321, U1504103).
B
Ling-Fa Lu [email protected] Ru-Bing Chen [email protected] Jin-Jiang Yuan [email protected] Li-Qi Zhang [email protected]
1
School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
2
College of Information and Management Science, Henan Agricultural University, Zhengzhou 450003, China
123
R.-B. Chen et al.
1 Introduction The integrated production and delivery scheduling problems have received a lot of attention from both industry practitioners and academic researchers. In order to save time and/or cost, the coordination between job production and job delivery has been widely discussed in literature. In the previous literature, there are two traditional methods to deliver all jobs. The first method always sends the finished jobs individually and immediately to their customers. It is generally assumed that there is a sufficient number of vehicles. The second method transports the finished jobs in batches to their customers. Clearly, the second method needs fewer vehicles and lower delivery costs than the first method. In this paper, we adopt the second method to deliver all jobs. The earliest scheduling problem with individual delivery was first studied by Potts [1]. The author investigated a single-machine scheduling problem with release dates and delivery times to minimize the makespan. For this problem, the author provided a 23 -approximation algorithm. Hoogeveen and Vestjens [2] studied the online version of the problem studied by Potts [1]. For this online problem, they provided a best √ ≈ 1.618. When restarts possible online algorithm with the competitive ratio of 5+1 2 are allowed to all jobs, van den Akker et al. [3] proposed a best possible online algorithm with the competitive ratio of 23 . Several scheduling problems with batch delivery w
Data Loading...
