Algorithms for the relaxed Multiple-Organization Multiple-Machine Scheduling Problem

In this paper we present the generalization of the relaxed Multi- Organization Scheduling Problem (α MOSP). In our generalized problem, we are given a set of organizations; each organization is comprised of a set of machines. We are interested in minimizing the global makespan while allowing a constant factor, α_O, degradation in the local objective of each organization and a constant factor, α_M, degradation in the local objective of each machine. Previous work on α MOSP have primarily focussed on the degree of co-operativeness only at organization level whereas the degree of co-operativeness of an individual machine is also equally important. We develop a general framework for building approximation algorithms for the problem. Using this framework we present a family of approximation algorithms with varying approximation guarantees on the global makespan and the degrees of cooperativeness of the machines and organizations. In particular, we present (4, 2, 3), (4, 3, 2) and (3, 3, 3) approximation results where the first, and second values in the triplet represent the degree of co-operativeness of the machines and the organizations respectively and the third value denotes approximation guarantee for the global makespan. We also present and experimentally analyze different heuristics to improve the global makespan once solutions with the above theoretical guarantees are obtained.