Single machine scheduling with batch deliveries. (English) Zbl 0947.90579

Summary: The single machine batch scheduling problem is studied. The jobs in a batch are delivered to the customer together upon the completion time of the last job in the batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and its completion time. The objective is to minimize the sum of the batch delivery and job earliness penalties. A relation between this problem and the parallel machine scheduling problem is identified. This enables the establishment of complexity results and algorithms for the former problem based on known results for the latter problem.


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


[1] Albers, S.; Brucker, P., The complexity of one-machine batching problems, Discrete applied mathematics, 47, 87-107, (1993) · Zbl 0792.90035
[2] Bruno, J.L.; Coffman, E.G.; Sethi, R., Scheduling independent tasks to reduce Mean finishing time, Communications of ACM, 117, 382-387, (1974) · Zbl 0283.68039
[3] Cheng, T.C.E.; Gordon, V.S., On 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.; Kahlbacher, H.G., Scheduling with delivery and earliness penalties, Asia-Pacific journal of operational research, 10, 145-152, (1993) · Zbl 0789.90041
[5] 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
[6] Coffman, E.G.; Nozarl, A.; Yannakakis, M., Optimal scheduling of products with two subassemblies on a single machine, Operations research, 37, 426-436, (1989) · Zbl 0672.90075
[7] Conway, R.W.; Maxwell, W.L.; Miller, L.W., Theory of scheduling, (1967), Addison-Wesley Reading, MA · Zbl 1058.90500
[8] Dessouky, M.I.; Lageweg, B.J.; Lenstra, J.K.; van de Velde, S.L., Scheduling identical jobs on uniform parallel machines, Statistica neerlandica, 44, 115-123, (1990) · Zbl 0716.90053
[9] Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling and scheduling, Annals of discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044
[10] Horn, W.A., Minimizing average flow time with parallel machines, Operations research, 21, 846-847, (1973) · Zbl 0259.90030
[11] Kovalyov, M.Y., “A rounding technique to construct approximation algorithms for knapsack and bin-packing type problems”, in submission. · Zbl 0865.90109
[12] Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart & Winston New York · Zbl 0358.68059
[13] Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G.; Shmoys, D.B., Sequencing and scheduling: algorithms and complexity, () · Zbl 0482.68035
[14] 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
[15] Nadeff, D.; Santos, C., One-pass batching algorithms for the one machine problem, Discrete applied mathematics, 21, 133-145, (1988) · Zbl 0661.90044
[16] Rothkopf, M.H., Scheduling independent tasks on parallel processors, Management science, 12, 437-447, (1966)
[17] Sahni, S., General techniques for combinatorial approximation, Operations research, 25, 920-936, (1977) · Zbl 0386.90048
[18] Shallcross, D., A polynomial algorithm for a one machine batching problem, Operations research letters, 11, 213-218, (1992) · Zbl 0760.90059
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.