In this talk we will present some resource allocation problems and proposed solutions in systems with compatibility constraints. These include practical systems that cannot be modeled by traditional queueing networks with distinct servers, like radio networks, switches with input queueing, databases with concurrency control and some parallel processing systems. A common characteristic of those systems is that the allocation of the capacity of the different servers cannot be done independently since certain groups of them are incompatible and mutually exclusive. A number of scheduling algorithms that achieve maximum throughput in the above systems have been proposed recently. In those approaches the scheduling requires the solution of combinatorial optimization problems that may be of prohibitive complexity in several cases. We will review these solutions and we will present a class of maximum throughput scheduling policies with linear complexity on the number of servers. They are based on a randomized, iterative algorithm in combination with an incremental updating rule for the service configuration. The proposed policy is of maximum throughput under some fairly general conditions satisfied by a class of randomized algorithms with linear complexity per iteration.