Minimizing Total Completion Time of Batch Scheduling with Nonidentical Job Sizes
2017
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 (FFI) lies in the interval \([\frac{109}{82}, \frac{2+\sqrt{2}}{2}]\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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
25
References
0
Citations
NaN
KQI