# Heuristic Method for Decision-Making in Common Scheduling Problems
## 6 Sample Scheduling Problem  
To illustrate the presented approach, let us consider, in a formal way, the following problem that belongs to the class described in Section 2. We consider a project consisting of tasks (jobs) where the possibility of starting a task depends on the completion of other tasks. Thus, tasks and the relationships between them are represented by a non-directed graph \(G\) = (_V,E_), where _V = {1,..., n}_ is the set of vertices and \(E\) is the set of edges. Vertex 1 is the starting point of the work. The edges represent jobs that must be performed. We consider that \(m\) executors (machines) \(M_{j}\) (_j = 1,...,m_) have to process \(n\) jobs \(J_{i}\) (_i = 1,..., n_). The machines are in parallel and unrelated. Jobs may be processed on any of the machines. It is assumed that job splitting is not allowed, so job processing cannot be interrupted and resumed at a later time. The jobs are dependent because precedence relationships between jobs are represented by the graph \(G\). Release dates \(r_{i}\), at which time job \(J_{i}\) becomes available for processing, are defined for all jobs and depend on the previously performed jobs according to the graph \(G\). Thus, they are dependent on process state \(s\), and therefore they are denoted as \(r_{i}(s)\). The deadlines for some of the jobs \(d(j)\) are given. Moreover, the production process may require a machine setup (not always for all machines). Setup cannot be interrupted before its completion. We consider that the time of setup is not known a priori and depends not only on the job sequence, but also on a set of previously performed jobs, because previously performed jobs may be used as a resource for machine setup. Resources can only be used by one machine at a time. An objective function should be specified. For example, it may be the makespan (minimum job completion time) or sum of the costs of performing a job. This problem can be treated as a problem belonging to the class of arc routing problems with deadlines and setups in which the time depends on the process state. An example of such a complex project is the construction of a headings network in preparatory work in mines. The set of headings in the mine must be driven in order to render the exploitation field accessible. The headings form a net formally (represented by a non-oriented multigraph \(G\) = (_W,C,P_), where the set of branches \(C\) and the set of nodes \(W\) represent the set of headings and the set of heading crossings, respectively). The project begins at time \(t_{0}=0\) in the initial indicated node and ends at the moment of execution of all headings. The heading can be made by an executor or working group of different efficiency and cost of performing. In particular, a specialized machine, i.e., a mining combine, is used. These working groups are more effective but their cost is much higher and a mining combine must be transported when driving starts at a different crossing than the one in which the machine is placed. A heading performing cannot be interrupted before its completion and can be done only by one working group at a time. The task of executing headings can be started if one of the adjacent headings is made. Thus, release dates \(r_{i}\) are not known a priori and depend on the previously performed jobs. Moreover, the formerly prepared plan of field exploitation causes due dates for some of the headings. In cases where a transport of mining combine is necessary, the shortest transportation route from the current crossing to the one from which the next heading performing should be started will be chosen. The transport route depends on the state of the whole system, since transport is possible only through completed headings. Thus, it is a problem with state-dependent resources. Moreover, this transport can be considered as machine setup. Decisions to assign a working group to another heading performing are always made after the completion of previous work by this team and the decision takes into account the business of all working groups.