Batch delivery scheduling with batch delivery cost on a single machine. (English) Zbl 1125.90018

Summary: We consider a scheduling problem in which \(n\) independent and simultaneously available jobs are to be processed on a single machine. The jobs are delivered in batches and the delivery date of a batch equals the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total weighted flow time and delivery cost. We first show that the problem is strongly NP-hard. Then we show that, if the number of batches is \(B\), the problem remains strongly NP-hard when \(B\leq U\) for a variable \(U\geq 2\) or \(B\geq U\) for any constant \(U\geq 2\). For the case of \(B\leq U\), we present a dynamic programming algorithm that runs in pseudo-polynomial time for any constant \(U\geq 2\). Furthermore, optimal algorithms are provided for two special cases: (i) jobs have a linear precedence constraint, and (ii) jobs satisfy the agreeable ratio assumption, which is valid, for example, when all the weights or all the processing times are equal.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI Link


[1] Albers, S.; Brucker, P., The complexity of one-machine batching problems, Discrete applied mathematics, 47, 87-107, (1993) · Zbl 0792.90035
[2] Cheng, T.C.E.; Kahlbacher, H.G., Scheduling with delivery and earliness penalties, Asia-Pacific journal of operational research, 10, 145-152, (1993) · Zbl 0789.90041
[3] Cheng, T.C.E.; Gordon, V.S., Batch delivery scheduling on a single machine, Journal of the operational research society, 45, 1211-1215, (1994) · Zbl 0814.90046
[4] Cheng, T.C.E.; Gordon, V.S.; Kovalyov, M.Y., Single machine scheduling with batch deliveries, European journal of operational research, 94, 277-283, (1996) · Zbl 0947.90579
[5] Cheng, T.C.E.; Kovalyov, M.Y.; Lin, B.M.T., Single machine scheduling to minimize batch delivery and job earliness penalties, SIAM journal on optimization, 7, 547-559, (1997) · Zbl 0874.68142
[6] Coffman, E.G.; Nozari, A.; Yannakakis, M., Optimal scheduling of products with two subassemblies on a single machine, Operations research, 37, 426-436, (1989) · Zbl 0672.90075
[7] Coffman, E.G.; Yannakakis, M.; Magazine, M.J.; Santos, C., Batch sizing and sequencing on a single machine, Annals of operations research, 26, 135-147, (1990) · Zbl 0712.90035
[8] Garey, M.R.; Johnson, D.S., A guide to the theory of NP-completeness, (1979), W.H. Freeman San Francisco, CA · Zbl 0411.68039
[9] Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of operations research, 5, 287-326, (1979) · Zbl 0411.90044
[10] Lawler, E.L.; Moore, J.M., A functional equation and its application to resource allocation and sequencing problems, Management science, 16, 77-84, (1969) · Zbl 0184.23303
[11] Naddef, D.; Santos, C., One-pass batching algorithms for the one-machine problem, Discrete applied mathematics, 21, 133-146, (1988) · Zbl 0661.90044
[12] Rothkopf, M.H., Scheduling independent tasks on parallel processors, Management science, 12, 437-447, (1966)
[13] Shallcross, D., A polynomial algorithm for a one machine batching problem, Operations research letters, 11, 213-218, (1992) · Zbl 0760.90059
[14] Smith, W.E., Various optimizers for single-stage production, Naval research logistics quarterly, 3, 59-66, (1956)
[15] Wang, G.Q.; Cheng, T.C.E., Parallel machine scheduling with batch delivery costs, International journal of production economics, 68, 177-183, (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.