“Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation |
| |
Authors: | C.T. Ng M.S. Barketau T.C.E. Cheng Mikhail Y. Kovalyov |
| |
Affiliation: | 1. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;2. United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus |
| |
Abstract: | Problem Product Partition differs from the NP-complete problem Partition in that the addition operation is replaced by the multiplication operation. Furthermore it differs from the NP-complete problem Subset Product in that it does not contain the product value B in its input. We prove that problem Product Partition and several of its modifications are NP-complete in the strong sense. Our results imply the strong NP-hardness of a number of scheduling problems with start-time-dependent job processing times and a problem of designing a reliable system with a series–parallel structure. It should be noticed that the strong NP-hardness of the considered optimization problems does not preclude the existence of a fully polynomial time approximation scheme (FPTAS) for them. We present a simple FPTAS for one of these problems. |
| |
Keywords: | Complexity theory Scheduling Subset Product FPTAS Systems reliability |
本文献已被 ScienceDirect 等数据库收录! |