Service Reliability in an HC: Considering From the Perspective of Scheduling With Load-Dependent Machine Reliability

Considering the fact that a server is more likely to fail if it is highly loaded, in this paper, we involve load impacts on service reliability in a heterogeneous cluster, where servers have load-dependent reliabilities and jobs have resource and execution interval demands. Specifically, each server is specified by a resource capacity and a workload limitation, i.e., the server is expected to perform reliably if its workload is less than the workload limitation. There is also a set of jobs needing to be executed on these servers. Each job is associated with a resource demand and an execution interval, i.e., the time interval that the job is planned to be executed. Our goal is to find a reliable schedule ofjobs to servers such that all servers' workload limitations are satisfied. The problem is proved to be strongly NP-complete, which implies that there is not even a pseudo-polynomial time algorithm. Hence, we try our best to find a reliable schedule. To solve the problem, we define a stereogram (specifically defined as a bipartite stereogram) and develop a bipartite stereogram matching-based scheduling method (BSMSM), which combines the matching of our constructed bipartite stereogram with reliable scheduling. Some theoretical results are also derived in this paper. We perform extensive random experiments and the results show that BSMSM can find reliable schedules, i.e., the workloads on all servers can be maintained to be less than or equal to the servers' workload limitations, to a large extent.