caa a22 4500 465774539 CHVBK 20180323111938.0 cr unu---uuuuu 170327e19901201xx s 000 0 eng 10.1007/BF02248589 doi (NATIONALLICENCE)springer-10.1007/BF02248589 Batch sizing and job sequencing on a single machine [Elektronische Daten] [E. Coffman Jr., M. Yannakakis, M. Magazine, C. Santos] We study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set ofn items, the algorithm runs inO(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called thebatch-sizing problem, runs inO(n logn) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1]. J.C. Baltzer AG, Scientific Publishing Company, 1990 Coffman Jr. E. AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut Yannakakis M. AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut Magazine M. Department of Management Sciences, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut Santos C. Department of Management Sciences, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 26/1(1990-12-01), 135-147 0254-5330 26:1<135 1990 26 10479 https://doi.org/10.1007/BF02248589 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02248589 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Coffman Jr E. AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 700 1- Yannakakis M. AT&T Bell Laboratories, 07974, Murray Hill, NJ, USA aut NATIONALLICENCE 700 1- Magazine M. Department of Management Sciences, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut NATIONALLICENCE 700 1- Santos C. Department of Management Sciences, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut NATIONALLICENCE 773 0- Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 26/1(1990-12-01), 135-147 0254-5330 26:1<135 1990 26 10479 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer