Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Combinatorial Optimization
Published in: Journal of Combinatorial Optimization 3/2021

20-05-2019

Batch scheduling of nonidentical job sizes with minsum criteria

Authors: Rongqi Li, Zhiyi Tan, Qianyu Zhu

Published in: Journal of Combinatorial Optimization | Issue 3/2021

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper concerns the problem of scheduling jobs with unit processing time and nonidentical sizes on single or parallel identical batch machines. The objective is to minimize the total completion time of all jobs. We show that the worst-case ratio of the algorithm based on the bin-packing algorithm First Fit Increasing lies in the interval \(\left[ \frac{109}{82}, \frac{2+\sqrt{2}}{2}\right] \approx [1.3293, 1.7071]\) for the single machine case, and is no more than \(\frac{6+\sqrt{2}}{4}\approx 1.8536\) for the parallel machines case.
previous article An improved algorithm for the -MaxSAT problem: asking branchings to satisfy the clauses
next article Improved algorithms for single vehicle scheduling on tree/cycle networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
Anily S, Bramel J, Simchi-Levi D (1994) Worst-case analysis of heuristics for the bin packing problem with general cost structures. Oper Res 42(2):287–298CrossRef
Balogh J, Békési J, Dósa G, Sgall J, van Stee R (2015) The optimal absolute ratio for online bin packing. In: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, pp 1425–1438
Boyar J, Dósa G, Epstein L (2012) On the absolute approximation ratio for First Fit and related results. Discrete Appl Math 160:1914–1923MathSciNetCrossRef
Brucker P, Gladky A, Hoogeveen H, Kovalyov MY, Potts CN, Tautenhahn T, van de Velde SL (1998) Scheduling a batching machine. J Sched 1:31–54MathSciNetCrossRef
Cheng B, Yang S, Hu X, Chen B (2012) Minimizing makespan and total completion time for parallel batch processing machines with non-identical job sizes. Appl Math Model 36(7):3161–3167MathSciNetCrossRef
Deng X, Feng H, Li G, Liu G (2002) A PTAS for minimizing total completion time of bounded batch scheduling. Int J Found Comput Sci 13:817–827MathSciNetCrossRef
Dósa G (2007) The tight bound of First Fit decreasing bin-packing algorithm is \(FFD(L)\le \frac{11}{9}OPT(L)+\frac{6}{9}\). Lect Notes Comput Sci 4614:1–11CrossRef
Dósa G, Sgall J (2013) First Fit bin packing: a tight analysis. In: Proceedings of the 30th symposium on theoretical aspects of computer science, pp 538–549
Dósa G, Tan ZY, Tuza Z, Yan Y, Lányi CS (2014) Improved bounds for batch scheduling with nonidentical job sizes. Naval Res Logist 61:351–358MathSciNetCrossRef
Garey MR, Johnson DS (1978) Computers and intractability: a guide to the theory of NP-completeness. Freeman, LondonMATH
Hochbaum DS, Landy D (1997) Scheduling semiconductor burn-in operations to minimize total flowtime. Oper Res 45(6):874–8859CrossRef
Johnson DS (1973) Near-optimal bin packing algorithms. Doctoral Thesis, MIT
Johnson DS, Demers A, Ullman JD, Garey MR, Graham RL (1974) Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J Comput 3:299–325MathSciNetCrossRef
Li S, Li G, Qi X (2006) Minimizing total weighted completion time on identical parallel batch machines. Int J Found Comput Sci 17(6):1441–1453MathSciNetCrossRef
Li S, Li G, Zhang S (2005) Minimizing makespan with release times on identical parallel batching machines. Discrete Appl Math 148:127–134MathSciNetCrossRef
Poon CK, Yu W (2004) On minimizing total completion time in batch machine scheduling. Int J Found Comput Sci 15(4):593–607MathSciNetCrossRef
Ullman JD (1971) The performance of a memory allocation algorithm. Technical Report 100, Princeton University
Uzsoy R (1994) A single batch processing machine with non-identical job sizes. Int J Prod Res 32:1615–1635CrossRef
Xia B, Tan ZY (2010) Tighter bounds of the First Fit algorithm for the bin-packing problem. Discrete Appl Math 158:1668–1675MathSciNetCrossRef
Metadata
Title
Batch scheduling of nonidentical job sizes with minsum criteria
Authors
Rongqi Li
Zhiyi Tan
Qianyu Zhu
Publication date
20-05-2019
Publisher
Springer US
Published in
Journal of Combinatorial Optimization / Issue 3/2021
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-019-00419-9

Other articles of this Issue 3/2021

Journal of Combinatorial Optimization 3/2021 Go to the issue

OriginalPaper

An improved mechanism for selfish bin packing

OriginalPaper

On the complexity of and algorithms for detecting k-length negative cost cycles

OriginalPaper

Improved algorithms for single vehicle scheduling on tree/cycle networks

OriginalPaper

A dynamic approach to detecting, eliminating and fixing memory leaks

Editorial

Preface: special issue on the annual international conference on combinatorial optimization and applications (COCOA)

OriginalPaper

On the price of anarchy of two-stage machine scheduling games

Premium Partner

    Image Credits