Cloud computing environments pose challenges in Parallel Batch Machine Scheduling (PBMS) with Malleable Jobs, which require the job width to be adjustable during execution, whereas the traditional problem considers only fixed job widths. In this paper, we propose a fast approximation algorithm with a runtime \(O(n \log n)\) and a ratio of \((4-\frac{2}{Km})\) , where \(n\) is the number of jobs, and \(K\) and \(m\) respectively denote machine capacities and numbers. This is achieved through employing the state-of-the-art scheduling algorithm by simply setting each job’s width to its maximum degree of parallelism, where we develop new proof techniques to demonstrate the ratio due to the nature of malleable jobs. We then refine the algorithm by leveraging the relationship between maximum job demand and average processing capacity per processor, achieving an improved ratio of \((4-\frac{4}{Km})\) while maintaining the \(O(n \log n)\) runtime efficiency. In addition, for jobs with identical release times, our algorithm can be fine-tuned to achieve a ratio of \((3-\frac{2}{Km})\) . Lastly, we further extend our algorithm to address the problem involving two machines with non-identical capacities, achieving a ratio of \(\frac{17}{5}\) and a runtime of \(O(n \log n)\) . This compares favorably with the previous state-of-the-art, which has a ratio of 5 and a runtime of \(O(n^2)\) .
