Improved bounds for batch scheduling with nonidentical job sizes
Authors:
- 29 May 2014
- journal article
- research article
- Published by Wiley in Naval Research Logistics (NRL)
- Vol. 61 (5) , 351-358
Abstract
Here, we revisit the bounded batch scheduling problem with nonidentical job sizes on single and parallel identical machines, with the objective of minimizing the makespan. For the single machine case, we present an algorithm which calls an online algorithm (chosen arbitrarily) for the one‐dimensional bin‐packing problem as a sub‐procedure, and prove that its worst‐case ratio is the same as the absolute performance ratio of . Hence, there exists an algorithm with worst‐case ratio , which is better than any known upper bound on this problem. For the parallel machines case, we prove that there does not exist any polynomial‐time algorithm with worst‐case ratio smaller than 2 unless P = NP, even if all jobs have unit processing time. Then we present an algorithm with worst‐case ratio arbitrarily close to 2. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 351–358, 2014Keywords
Funding Information
- Gyorgy Dosa
- Chinese-Hungarian bilateral (TET-12-CN-1-2012-0028, TAMOP-4.2.2.A-11/1/KONV-2012-0072)
- National Natural Science Foundation of China (10971191, 11271324)
- Zhejiang Provincial Natural Science Foundation of China (LR12A01001)
- Fundamental Research Funds for the Central Universities
- Hungarian Scientific Research Fund, OTKA (T-81493, TAMOP-4.2.2.A-11/1/KONV-2012-0072)
This publication has 19 references indexed in Scilit:
- On the absolute approximation ratio for First Fit and related resultsDiscrete Applied Mathematics, 2012
- New lower bounds for certain classes of bin packing algorithmsTheoretical Computer Science, 2012
- The Tight Bound of First Fit Decreasing Bin-Packing Algorithm Is FFD(I) ≤ 11/9OPT(I) + 6/92007
- Scheduling a batching machineJournal of Scheduling, 1998
- Using dual approximation algorithms for scheduling problems theoretical and practical resultsJournal of the ACM, 1987
- Efficient scheduling algorithms for a single batch processing machineOperations Research Letters, 1986
- A simple on-line bin-packing algorithmJournal of the ACM, 1985
- Worst-Case Performance Bounds for Simple One-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1974
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969
- Bounds for Certain Multiprocessing AnomaliesBell System Technical Journal, 1966