The multifit algorithm for set partitioning containing kernels. (English) Zbl 0951.90020
Summary: This paper investigates the set partitioning containing kernels. This problem can also be considered as the identical machine scheduling problem with nonsimultaneous machine release times. That the algorithm MULTIFIT has a worst case bound of \(6/5\) is proved. Through combining MULTIFIT and LPT, an algorithm MULTILPT with a worst case bound of \(7/6\) has been obtained.
References:
| [1] | Chen, S. P., He, Y. and Yao, E. Y., Three-partioning containing kernels: Complexity and heuristic, Computing, 1996, 57: 255–271. · Zbl 0856.90059 · doi:10.1007/BF02247409 |
| [2] | Yao, E. Y., Li, R. H. and He, Y., New progress on optimal partitioning problem, In: K. H. Phua, et al eds., Optimization Techniques and Applications, ICOTA’92, World Scientific, Singapore, 1992, 229–235. |
| [3] | Garey, M. R. and Johnson, D. S., Computers and intractability: A guide to the theory of NP-Completeness, Freeman, San Francisco, 1979. · Zbl 0411.68039 |
| [4] | Lee, C. Y., Parallel machines scheduling with nonsimultaneous machine available times. Discrete Appl. Math., 1991, 30: 53–61. · Zbl 0722.90032 · doi:10.1016/0166-218X(91)90013-M |
| [5] | Lin, G. H., He, Y., Lu, H. Y., et al., Exact bounds of the modified LPT algorithm applying to parallel machines scheduling with nonsimultaneous machine available time, Appl. Math.-JCU Ser. B, 1997, 12: 109–118. · Zbl 0884.90104 |
| [6] | He, Y., Kellerer, H. and Kotov, V., Linear compound algorithms for the partitioning problem, submitted for publication. · Zbl 0991.90070 |
| [7] | Li, R. H., Multifit algorithm for parallel machine scheduling with nonsimultaneous machine available time, Manuscript, 1996. |
| [8] | Chang, S. Y., Hwang, H., The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines, Manuscript, Pohang University of Science and Technology, South Korea, 1996. · Zbl 0931.68017 |
| [9] | Coffman, E. G., Garey, M. R. and Johnson, D. S., An application of bin packing to multiprocessor scheduling, SIAM J. Comput. 1978, 7: 1–17. · Zbl 0374.68032 · doi:10.1137/0207001 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
