Analysis of Complex Networks

12.1 Introduction

Scheduling theory is one of those mathematical disciplines that are focused on real-life applications [1,2]. Its main feature is consideration and optimization of various processes running in time. Basically we speak about discrete mathematical models of those processes and discrete optimization problems targeted to optimize some characteristics of those processes. Each such optimization problem can be solved by different algorithms [3], but for real-life applications it is essential that the algorithm be efficient in running time and required memory [4]. Designing such algorithms is one of the main objectives of discrete optimization in general and scheduling theory in particular [5, 6].

It is clear that nowadays the variety of processes organized to serve various human demands is so huge that practically, to model those processes, one has to involve the whole pool of mathematical tools and models. That is why the main feature of scheduling theory is a huge variety of different models. It would not be exaggerating to say that, practically, scheduling theory contains the whole Discrete Mathematics inside. And one of the most popular tools being explored in scheduling theory is the model of graph [7, 8].

Different types of graphs are used for convenient visualization of various constraints imposed on feasible solutions. Normally, the more general the type of graph that is used, the more time is required to verify those constraints specified by the graph. As a rule, ...