We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the long...We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS) for this problem.展开更多
基金supported by the National Natural Science Foundation of China(Nos.62225304,61933001,62173031,U20A20225)the Interdisciplinary Research Project for Young Teachers of Fundamental Research Funds for the Central Universities (No.FRF-IDRY-22-029)the Beijing Top Discipline for Artificial Intelligent Science and Engineering,University of Science and Technology Beijing。
文摘We sttidy the problem of scheduling n jobs on m parallel bounded batch machines to minimize the sum of squared machine loads. Each batch contains at most B jobs, and the processing time of a batch is equal to the longest processing time of the jobs in this batch. We prove this problem to be NP-hard. Furthermore, we present a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS) for this problem.