\documentclass[twoside,11pt]{article}
%\documentclass[jair,twoside,11pt]{article}
\input epsf %% at top of file
\usepackage{theapa}
\usepackage{jair}

\jairheading{19}{2003}{73-138}{12/02}{8/03}
\ShortHeadings{Optimal Schedules for Parallelizing Anytime Algorithms}
{Finkelstein, Markovitch \& Rivlin}
\firstpageno{73}

\usepackage{epsfig}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{amsthm}

\begin{document}

\title{Optimal Schedules for Parallelizing Anytime Algorithms:\\
 The Case of Shared Resources}
\author{\name Lev Finkelstein\email lev@cs.technion.ac.il\\  
       \name Shaul Markovitch \email shaulm@cs.technion.ac.il\\ 
       \name Ehud Rivlin \email ehudr@cs.technion.ac.il \\ 
       \addr Computer Science Department \\ 
       Technion - Israel Institute of Technology\\ 
       Haifa 32000, Israel} 

\include{my_macros}
\include{my_macros2}
\newcommand{\myfullciteauthor}[2]{\fullciteauthor{#2}~\citeyear{#2}}
%\newcommand{\fullciteauthor}[2]{\citeauthor{#2}~\shortcite{#2}}
%\newcommand{\fullciteauthor}[2]{{#1}~\cite{#2}}
%\newcommand{\shortcite}[1]{~\cite{#1}}

\newcommand{\calA}{{\cal A}}
\newcommand{\calR}{{\cal R}}
\newcommand{\calRP}{{\cal R}^{+}}
\newcommand{\calS}{{\cal S}}

\maketitle
\begin{abstract}
The performance of anytime algorithms
can be improved by  simultaneously solving 
several instances of algorithm-problem pairs. 
These pairs may include different instances of a problem 
(such as starting from a different initial state), different algorithms
(if several alternatives exist), or several runs of the
same algorithm (for
non-deterministic algorithms).
In this paper we present a methodology for designing an
optimal scheduling policy based on the statistical characteristics of the
algorithms involved. We formally analyze the case where the processes share resources 
(a single-processor model), and provide an algorithm for optimal scheduling.
We analyze, theoretically and empirically, the behavior
of our scheduling algorithm for various distribution types.  Finally,
we present empirical results of applying our scheduling algorithm
to the Latin Square problem.  

\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

Assume that our task is to learn a concept with a predefined success rate,
measured on a given test set. Assume that we can use two alternative
learning algorithms, one which learns fast but requires some preprocessing,
and another which works more slowly but requires no preprocessing.
Can we possibly benefit 
from using \emph{both} learning algorithms in parallel 
to solve \emph{one} learning task on a single-processor machine? 

Another area of application is that of constraint satisfaction problems.  
Assume that 
a student tries to decide between two elective courses by trying
to schedule each of them with the set of her compulsory courses.
Should the student try to solve the two sets of constraints sequentially
or should the two computations be somehow interleaved?

Assume now that a crawler searches for a specific page in a site. If we had
more than one starting point, the process could be speeded up by
simultaneous application of the crawler from a few (or all) of them. However,
what would be the optimal strategy if the bandwidth were restricted?

What do the above examples have in common?
\begin{itemize}
\item There are potential benefits to be gained from the uncertainty in
the amount of resources that will be required to solve more than one 
instance of the algorithm-problem pair.
We can use different algorithms (in the first example) and different problems 
(in the last two examples). 
For non-deterministic algorithms, we can also use different runs of the
same algorithm.
\item Each process is executed with the purpose of satisfying a
given goal predicate. The task is considered accomplished when one of the
runs succeeds.
\item If the goal predicate is satisfied at time $t^*$, then it is also
satisfied at any time $t>t^*$. This property is equivalent
to utility monotonicity
of~\emph{anytime algorithms}~\cite{Dean:1988:ATDP,Horvitz:1987:RBACRC},
where solution quality is restricted to Boolean values.
\end{itemize}

Our objective is to provide a schedule that minimizes the expected cost,
possibly under some constraints (for example, processes
may share resources). Such problem definition is typical
for \emph{rational-bounded} 
reasoning~\cite{Simon:1982:MBR,Russell:1991:DRT}.
This problem resembles those faced  by
\emph{contract algorithms}~\cite{Russell:1991:CRTS,Zilberstein:1993:PHD}.
There, given the allocated resources, the task is to construct
an algorithm providing a solution of the highest quality. In our case, 
given quality requirements, the task is to construct an algorithm that
solves the problem using minimal resources. 

There are several research works that deal with similar problems.
Simple parallelization, with no information exchange between the processes,
may speed up the process due to high diversity in solution times. For example,
\myfullciteauthor{Knight}{Knight:1993:MRA} showed that using many reactive 
agents employing 
\rta\ search~\cite{Korf:1990:RTH} is more beneficial than using a single 
deliberative agent.
Another example is the work of
\myfullciteauthor{Yokoo and Kitamura}{Yokoo:1996:MRT}, who used several 
search agents in parallel, with agent rearrangement after 
preallotted periods of 
time. \myfullciteauthor{Janakiram {\em et al.}}{Janakiram:1988:RPB} 
showed that 
for many common distributions of solution time, simple parallelization leads 
to at most linear speedup.  
One exception is the family of  \emph{heavy-tailed} 
distributions~\cite{Gomes:1998:BCS} for which it is
possible to obtain superlinear speedup by simple 
parallelization.

A superlinear speedup can also be obtained 
when we have access to the internal structure of the processes involved.
For example, \myfullciteauthor{Clearwater {\em et al.}}{Clearwater:1992:CPS}
reported superlinear speedup for cryptarithmetic problems as a result of
information exchange between
the processes.  Another example is the works of 
Kumar and Rao~\shortcite{Rao:1987:PDF,Kumar:1987:PDF,Rao:1993:EPB},
devoted to parallelizing standard search algorithms, where superlinear speedup
is obtained by dividing the search space.

An interesting domain-independent approach 
is based on ``portfolio'' construction
\cite{Huberman:1997:EAH,Gomes:1997:APD}. 
In this approach, a different amount of resources is allotted to each
process. This can reduce both expected resource consumption and its variance. 

In the case of non-deterministic algorithms, another way to benefit from 
solution time diversity is to restart the same algorithm in attempt
to switch to a better trajectory. Such a framework was analyzed in detail
by~\myfullciteauthor{Luby \emph{et al.}}{Luby:1993:OSL} for the case
of a single processor 
and by~\myfullciteauthor{Luby and Ertel}{Luby:1994:OPL} for
the multiprocessor case. In particular, it was proven that for a single 
processor, the optimal strategy is to periodically restart the 
algorithm after a constant amount of time until the solution is found. 
This strategy was 
successfully applied to combinatorial search problems
by~\myfullciteauthor{Gomes \emph{et al.}}{Gomes:1998:BCS}. 

There are several settings, however, where the restart strategy is
not optimal. 
If the goal is to schedule a number of runs of a single
non-deterministic algorithm, such that this number is limited 
due to the nature of the problem (for example, robotic search),
the restart strategy is applicable but not optimal.
A special case of the above settings is scheduling
 a number of runs
of a deterministic algorithm with a finite set of
available initial configurations (inputs).
Finally,  the  case where the goal is to schedule a set of algorithms 
 different from each other is out of the scope of the restart strategy.

The goal of this research is to develop a methodology for designing an
optimal scheduling policy for any number of instances of algorithm-problem
pairs, where the algorithms can be 
either deterministic or non-deterministic.
We present a formal framework for scheduling parallel 
anytime algorithms for the case where the processes share resources 
(a single-processor model),
 based on the statistical characteristics of the
algorithms involved. 
The framework assumes that we know the probability of the goal condition
to be satisfied as a function of time (a
{\em performance profile}~\cite{Simon:1955:BMRC,Boddy:1994:DTDS}
restricted to Boolean quality values).
We analyze the properties of optimal schedules for the suspend-resume model,
where allocation of resources is performed on mutual exclusion basis,
and show that in most cases an extension of the framework to intensity control,
where resources may be allocated simultaneously and proportionately to
multiple demands,
does not yield better schedules. We also present an algorithm
for building optimal schedules. Finally, we demonstrate experimental results
for the optimal schedules.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Motivation}
Before starting the formal discussion, we would like to 
illustrate how different 
scheduling strategies can affect the performance of
a system of two search processes.
The first example has a very simple setup which allows us to perform a full
analysis.  In the second example,
we show quantitative results for a real CSP problem.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Scheduling DFS Search Processes}
Assume  DFS with random tie-breaking
is applied to a simple search space shown in 
Figure~\ref{fig:three-paths:example}, but that only
two runs of the algorithm are allowed\footnote{
Such a limit can follow, for example, from physical constraints,
such as for the problem of robotic search.
For unlimited number of runs
the optimal results would be provided by the restart strategy.
}. 
There is a very large number of paths to the goal, half of them of length 10,
quarter of them of length 40, and quarter of them of length 160.
When one of the processes finds the solution, the task is considered 
accomplished. 
\begin{figure}[htbp] 
\begin{center}
\psfig{figure=figures/npaths3.eps,width=0.8\columnwidth}
\caption{\label{fig:three-paths:example}
\small
A simple search task: two DFS-based agents  search for a path from $A$ to
 $B$. Scheduling the processes may reduce costs.
}
\end{center}
\end{figure}

We consider a single-processor system, where the two processes cannot
run simultaneously. Let us denote the processes by $A_1$ and $A_2$,
and by $L_1$ and $L_2$ the actual path lengths for $A_1$ and $A_2$ respectively
for the particular run.

The application of a single processes (without loss of generality, $A_1$)
gives us the expected execution time of
$1/2\times 10 + 1/4\times 40 + 1/4\times 160 = 55$, as is shown in
Figure~\ref{fig:three-paths:single}.
\begin{figure}[htbp] 
\begin{center}
\input{figures/npath3-single.tex}
\caption{\label{fig:three-paths:single}
\small
Path lengths, probabilities and costs for running a single process
}
\end{center}
\end{figure}

We can improve the performance by simulating a simultaneous execution of two
processes. For this purpose, we allow each of the processes to expand
a \emph{single} node, and to switch to the other process (without
loss of generality, $A_1$ starts first). In this case,
the expected execution time is
$1/2\times 19 + 1/4\times 20 + 1/8\times 79 + 1/16\times 80 + 1/16\times 319 =
49.3125$, as is shown in Figure~\ref{fig:three-paths:simultaneous}.
\begin{figure}[htbp] 
\begin{center}
\input{figures/npath3-simultaneous.tex}
\caption{\label{fig:three-paths:simultaneous}
\small
Path lengths, probabilities and costs for simulating a simultaneous execution
}
\end{center}
\end{figure}

Finally, if we know the distribution of path lengths, we can allow
$A_1$ to open $10$ nodes; if $A_1$ fails, we can stop it and allow $A_2$ to 
open $10$ nodes; if $A_2$ fails as well, we can allow $A_1$ to open
the next $30$ nodes, and so forth. In this scenario, $A_1$ and $A_2$
switch after $10$ and $40$ nodes (if both processes fail to find
a solution after $40$ nodes, it is guaranteed to be found by $A_1$ after
$160$ nodes). This scheme is shown in
Figure~\ref{fig:three-paths:interleaved}, and the expected time
is
$1/2\times 10 + 1/4\times 20 + 1/8\times 50 + 1/16\times 80 + 1/16\times 200 =
33.75$.
\begin{figure}[htbp] 
\begin{center}
\input{figures/npath3-interleaved.tex}
\caption{\label{fig:three-paths:interleaved}
\small
Path lengths, probabilities and costs for the interleaved execution
}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{The Latin Square Example}
\label{sec:LS}
The task in the Latin Square problem is to place $N$ symbols on
an $N \times N$ square such that each 
symbol appears only once in each row and each column. An example is shown
in Figure~\ref{fig:latin:square}.
\begin{figure}[htbp] 
\begin{center}
\[
\begin{array}{|c|c|c|c|c|}\hline
1 & 2 & 3 & 4 & 5 \\\hline
3 & 4 & 5 & 1 & 2 \\\hline
5 & 1 & 2 & 3 & 4 \\\hline
2 & 3 & 4 & 5 & 1 \\\hline
4 & 5 & 1 & 2 & 3 \\\hline
\end{array}
\]
\caption{\label{fig:latin:square}
\small
An example of a $5\times 5$ Latin Square.
}
\end{center}
\end{figure}

A more interesting problem arises when the square is partially filled.
The problem in this case may be solvable (see the left side of
Figure~\ref{fig:ls:solvable}) or unsolvable (see the right side of
Figure~\ref{fig:ls:solvable}).
\begin{figure}[htbp] 
\begin{center}
\begin{tabular}{cc}
\mbox{$
\begin{array}{|c|c|c|c|c|}\hline
1 &   &   &   &   \\\hline
  & 4 &   & 1 &   \\\hline
5 &   & 2 &   &   \\\hline
  &   &   &   & 1 \\\hline
  &   & 1 & 2 &   \\\hline
\end{array} 
$}
&
\mbox{$
\begin{array}{|c|c|c|c|c|}\hline
1 &   & ? & 4 & 5 \\\hline
  &   &   &   &   \\\hline
  & 2 &   &   &   \\\hline
  & 3 &   &   &   \\\hline
  &   & 4 &   &   \\\hline
\end{array} 
$}
\end{tabular}
\caption{\label{fig:ls:solvable}
\small
An example of solvable (to the left) and unsolvable (to the right) prefilled
$5\times 5$ Latin Squares.
}
\end{center}
\end{figure}
The problem of satisfiability of a partially filled Latin Square is
a typical constraint-satisfaction problem. We consider a slight variation of
this task. Let us assume that \emph{two} partially filled squares are 
available, and we need to decide whether at least one of them is solvable.
We assume that we are allocated a single processor. We attempt to 
speed up the time of finding a solution by starting to solve the two 
problems from two different initial configurations in parallel.


Each of the processes employs a deterministic 
heuristic DFS with the First-Fail 
heuristic~\cite{Gomes:1997:APD}.  We consider $10\%$-filled 
$20 \times 20$ Latin Squares.
The behavior of a single process measured on a set of
  50,000 randomly generated samples is shown in Figure \ref{fig:LS:Ff}.
Figure \ref{fig:LS:Ff}(a) shows the probability of finding a solution
as a function of the number of search steps, and Figure \ref{fig:LS:Ff}(b)
shows the corresponding distribution density.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[htbp] 
\twofigbox{figures/LATIN_SQUARE/LS_F.eps}{figures/LATIN_SQUARE/LS_ff.eps}
\caption{\label{fig:LS:Ff}
\small The behavior of DFS with the First-Fail heuristic on 
$10\%$-filled 
$20 \times 20$ Latin Squares.
 (a)~The probability of finding a solution as a function of the number
of search steps; (b)~The corresponding distribution density.
}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Assume that each run is limited to 25,000 search steps 
(only 88.6\% of the problems
are solvable under this condition).
If we apply the algorithm only on one of the available two initial
configurations, the average number of search steps is 3777.
If we run two processes in parallel (alternating after each step),
we obtain a result of 1358 steps.  
If we allow a single switch at the \emph{optimal} point 
(an analogue of the restart
technique~\cite{Luby:1993:OSL,Gomes:1998:BCS} for two processes),
we get 1376 steps on average (the optimal point is after 1311 steps).
Finally, if we interleave the processes, switching at the points corresponding
to 679, 3072, and 10208 of total steps, 
the average number of steps is 1177.
The above results were averaged over a test set of 25,000 pairs
of initial configurations.

The last sequence of switch points is an optimal schedule for
the process with behavior described by the graphs in Figure \ref{fig:LS:Ff}.
In the rest of the paper we present an algorithm for deriving such 
optimal schedules.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{A Framework for Parallelization Scheduling}
In this section we formalize the intuitive description of parallelization
scheduling. The first part of this framework is similar to our framework
presented in~\cite{Finkelstein:2001:OSM}.

Let $\calS$ be a set of states, $t$ be a time variable with 
non-negative real values, and $\calA$ be a random process such that each 
realization (trajectory) $A(t)$ of $\calA$ represents a mapping from 
$\calRP$ to $\calS$.  Let $X_0$ be a random variable defined over $\calS$.
  Since an algorithm $Alg$ 
starting from an initial
state $S_0$ corresponds to a single trajectory (for
deterministic algorithms), or to a set of trajectories with an 
associated distribution (for non-deterministic algorithms),
 the pair $\langle X_0, Alg \rangle$, where $X_0$ stands
for the initial state,
can be viewed as a random process.
Drawing a trajectory for such a process corresponds, without
loss of generality, to a two-step procedure: first an initial
state $S_0$ is drawn for $X_0$, and then a trajectory $A(t)$ 
starting from $S_0$ is
drawn for $Alg$.
Thus, the source of randomness is either the randomness of the
initial state, or the randomness of the algorithm (which can come
from the algorithm itself or from the environment), or both.
 


Let $\calS^* \subseteq \calS$ be a designated set
of states, and $G : \calS \rightarrow \{0, 1\}$ be the characteristic 
function of $\calS^*$ called the
{\em goal predicate}.  The behavior of a trajectory $A(t)$ of $\calA$
with respect to the goal predicate $G$ can be written as $G(A(t))$,
which we denote by $\widehat{G_A}(t)$.
We say that $\calA$ is \emph{monotonic} over $G$ if and only if
$\widehat{G_A}(t)$ is
a non-decreasing function 
for each trajectory $A(t)$ of $\calA$.
 Under the above assumptions $\widehat{G_A}(t)$ is
 a step function with at most one discontinuity point.

Let $\calA$ be monotonic over $G$. From the definitions above
we can see that the behavior of $G$ for each trajectory $A(t)$ of $\calA$  
can be described by a single point $\widehat{t}_{A,G}$,  the first point 
after which the goal predicate is true, i.e, 
$\widehat{t}_{A,G}=\inf_t\{t | \widehat{G_A}(t) = 1\}$. 
If $\widehat{G_A}(t)$ 
is always $0$, we say that $\widehat{t}_{A,G}$ is not defined. 
Therefore, we can define a random variable, which for each trajectory 
$A(t)$ of $\calA$ with $\widehat{t}_{A,G}$ defined, corresponds to 
$\widehat{t}_{A,G}$. 
The behavior of this variable can be described by its
distribution function  $F(t)$.
At the points where $F(t)$ is differentiable, we use the probability
density $f(t) = F'(t)$.

It is important to note that in practice not every trajectory of $\calA$
leads to the goal predicate satisfaction even after infinitely large time.
That means that the set of the trajectories where $\widehat{t}_{A,G}$ is
undefined is not necessarily of measure zero. That is why we define
the {\em probability of success\/} $p$ as the
 probability of $A(t)$ to have $\widehat{t}_{A,G}$
defined\footnote{Another way to express the possibility that a process will
not reach a goal state is to use $F(t)$ that approach  $1-p$ when 
$t\rightarrow\infty$. We prefer to use $p$ explicitly because 
the distribution function must meet the requirement 
$\lim_{t\rightarrow\infty}F(t) = 1$.}.
For the Latin Square example described in Section \ref{sec:LS},
the probability of success is $0.886$, and the graphs in
Figure \ref{fig:LS:Ff} correspond to $pF(t)$ and $pf(t)$. 

Assume now that we have a system of 
$n$ random processes $\calA_1, \ldots \calA_n$
with  corresponding distribution functions $F_1, \ldots, F_n$ and
goal predicates $G_1, \ldots, G_n$.
If the distribution functions $F_i$ and $F_j$ are identical, we refer to
$\calA_i$ and $\calA_j$ as \emph{$F$-equivalent}.

We define a \emph{schedule} of the system as a set of binary
functions $\{\theta_i\}$,
where at each moment $t$, the $i$-th process is active if
$\theta_i(t)=1$ and idle otherwise. We refer to this scheme as
\emph{suspend-resume} scheduling.
A possible generalization of this framework is to 
extend the suspend/resume control to 
a more refined mechanism that allows us to determine the {\em intensity\/}
with which each process acts. For software processes, this means varying
the fraction of CPU utilization; for tasks
like robot navigation this implies changing the speed of
the robots. Mathematically, using intensity control is equivalent to
replacing the binary functions $\theta_i(t)$ with continuous functions with
a range between zero and one\footnote{A special case of such a setup using
constant intensities was described by \myfullciteauthor{Huberman
\emph{et al.}}{Huberman:1997:EAH}.}.

Note that scheduling makes the term \emph{time} ambiguous.
On one hand, we have the \emph{subjective} time for each process,
consumed only when the process is active.  This kind of time corresponds to
some resource consumed by the process. On the other hand, we have an
\emph{objective} time measured from the point of view of an external
observer. The distribution function $F_i(t)$ of each process is defined over 
its subjective time, while the cost function (see below)
may use both kinds of times.  Since we are using several processes,
all the formulas in this paper
are based on the objective time.

Let us denote by $\sigma_i(t)$ the total time that  process $i$ has been 
active before $t$. By definition, 
\begin{equation}
\sigma_i(t) = \int_0^t \theta_i(x) {dx}.
\label{eq:sigma}
\end{equation}
In practice $\sigma_i(t)$ provides the mapping from the objective time 
$t$ to the subjective time of the $i$-th process, and we refer to these 
functions as \emph{subjective schedule functions}.
 Since $\theta_i$ can be obtained from
$\sigma_i$ by differentiation, we often 
describe schedules by $\{\sigma_i\}$ instead of $\{\theta_i\}$.

The processes $\{\calA_i\}$ with goal predicates $\{G_i\}$ running under
schedules $\{\sigma_i\}$ result in a new process
$\calA$, with a goal predicate $G$. $G$ is the disjunction of 
$G_i$ ($G(t) = \bigvee_i G_i(t)$), and therefore $\calA$ is monotonic over
$G$. We denote the distribution function of the corresponding random variable
by $\Fns$, and the corresponding distribution density by $\fns$.


Assume that we are given a monotonic non-decreasing {\em cost} 
function $u(t, t_1, \ldots, t_n)$, which depends on the objective time $t$
and the subjective times per process $t_i$. 
We also assume that $u(0, t_1, \ldots, t_n) = 0$.
Since the subjective times
can be calculated by $\sigma_i(t)$, we actually have 
$u = u(t, \sigma_1(t), \ldots, \sigma_n(t))$.

The \emph{expected} cost of schedule $\{\si\}$ can be expressed, therefore,
as\footnote{The generalization to the case where the probability of success
$p$ is not $1$ is considered at the end of the next section.}
\begin{equation}
\Eus = \int_{0}^{+\infty}u(t, \sigma_1, \ldots, \sigma_n) \fns\dt
\label{eq:settings:eu}
\end{equation}
(for the sake of readability, we omit $t$ in $\sigma_i(t)$).
Under the suspend-resume model assumptions, $\si$ must be differentiable
(except for a countable set of process switch points) and have
derivatives of $0$ or $1$ that would ensure correct
values for $\theta_i$. Under intensity control assumptions, the
derivatives of $\si$ must lie between $0$ and $1$.

We consider two alternative 
setups for resource sharing between the processes:
\begin{enumerate}
\item The processes share resources on a mutual exclusion basis.  That
means that exactly one process can be active at each moment, and
the processes will be active one after another until the goal is reached by one
of them. In this case the sum of derivatives of $\sigma_i$
is always one\footnote{This fact is obvious for the case of suspend-resume 
control, and
for intensity control it is reflected in Lemma~\ref{lemma:max:resources}.}.
The case of shared resources corresponds to the case of several processes 
running on a single processor.
\item The processes are fully independent: there are no additional
constraints on $\si$. This case corresponds to $n$ independent processes 
 running on $n$ processors.
\end{enumerate}
Our goal is to find a schedule which minimizes the 
expected cost~\eq{eq:settings:eu}
under the corresponding constraints.
The current paper is devoted to the case of shared processes.
The case of independent resources was studied in~\cite{Finkelstein:2002:OSPI}.


The scheduled algorithms considered in this framework
can be viewed as anytime algorithms.
The behavior of anytime algorithms is usually characterized
by their performance profile -- the expected quality 
of the algorithm output as a function of the alloted resources.
The goal predicate $G$
can be viewed as a quality function with two possible values, 
and thus the distribution function $F(t)$ meets the definition
of performance profile, where time plays the role of resource.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Suspend-Resume Based Scheduling}
\label{sec:suspend:resume}
In this section we consider the case of suspend-resume based control
($\si$ are continuous functions with derivatives $0$ or $1$).
\begin{claim}\label{claim:suspend}
The expressions for the goal-time distribution $\Fns$ and
the expected cost $\Eus$ are as follows\footnote{$u'_t$ and $u'_{\si}$ stand 
for partial derivatives of $u$ by $t$ and by $\si$ respectively.}:
\begin{gather}
\Fns = 1 - \prod_{i=1}^n (1-F_i(\si)),
\label{eq:Fns:sigma}\\
\Eus = \int_0^{+\infty}\left(u'_t + \sum_{i=1}^n \si' u'_{\si}\right)
\prod_{i=1}^n(1-F_i(\si))\dt.
\label{eq:Eus:sigma}
\end{gather}
\end{claim}
\begin{proof}
Let $t_i$ be the time it would take the $i$-th process to meet the goal if 
acted alone (if the process fails to reach the goal,
we consider $t_i=\infty$). Let $t^*$ be the time it takes the
system of $n$ processes to reach the goal. 
In this case, $t^*$ is distributed according to
$\Fns$, and $t_i$ are distributed according to $F_i(t)$.
Thus, because the processes, given a schedule, are independent,
we obtain
\begin{equation*}
\begin{split}
&F_n(t, \sigma_1, \ldots, \sigma_n) = P(t^* \leq t) = 1 - P(t^* > t) =
1 - P(t_1 > \sigma_1(t)) \times\ldots\times P(t_n > \sigma_n(t)) =\\
& 1 - (1 - F_1(\sigma_1(t)))\times\ldots\times (1-F_n(\sigma_n(t))) =
1 - \prod_{i=1}^n (1-F_i(\sigma_i(t))),
\end{split}
\end{equation*}
which corresponds to~\eq{eq:Fns:sigma}.
Since $F(t)$ is a distribution over time, we assume
$F(t) = 0$ for $t\leq 0$.
%%%%%

The average cost function will therefore be
\begin{equation*}
\begin{split}
&\Eus = \int_{0}^{+\infty}u(t,\sigma_1,\ldots,\sigma_n)\fns\dt = \\
&-\int_{0}^{+\infty}u(t,\sigma_1,\ldots,\sigma_n)\dd(1-\Fns) =\\
&-\boundbar{u(t,\sigma_1,\ldots,\sigma_n)(1-\Fns)}{0}{\infty} +
\int_0^{+\infty}\frac{du(t,\sigma_1,\ldots,\sigma_n)}{dt}
\prod_{i=1}^n(1-F_i(\sigma_i))\dt.
\end{split}
\end{equation*}
Since $u(0, \sigma_1,\ldots,\sigma_n) = 0$ and 
$F_n(\infty,\sigma_1,\ldots,\sigma_n) = 1$, the first term in the last 
expression is $0$. Besides, since the full derivative of $u$ by $t$
can be written as
\begin{equation*}
\frac{du(t,\sigma_1,\ldots,\sigma_n)}{dt} = u'_t + \sum_{i=1}^n \si' u'_{\si},
\end{equation*}
we obtain
\begin{equation*}
\Eus = \int_0^{+\infty}\left(u'_t + \sum_{i=1}^n \si' u'_{\si}\right)
\prod_{i=1}^n(1-F_i(\sigma_i))\dt,
\end{equation*}
which completes the proof.
\end{proof}
Note that in the case of $\sigma_i(t) = t$ and $F_i(t) = F(t)$
for all $i$ (parallel application of $n$ $F$-equivalent processes), we obtain
the
formula presented in~\cite{Janakiram:1988:RPB}, i.e., 
$F_n(t) = 1 - (1-F(t))^n$.

In the rest of this section  we show a formal solution
(necessary conditions and an algorithm) for the framework with shared
resources. We start with two processes and present the formulas and the algorithm, 
and then generalize the solution for an arbitrary number of processes.
 For the case of two processes, we only assume that $u$ is differentiable.
 
For the more elaborated setup of $n$ processes, we assume 
 that the total cost is a linear combination of
the objective time and all the subjective times, and 
the subjective times are of the same weight:
\begin{equation}
u(t, \sigma_1, \ldots, \sigma_n) = at + b\sum_{i=1}^n \sigma_i(t).
\label{eq:u:linear}
\end{equation}
Since time is consumed if and only if there is an active process, and
the trivial case where all the processes are idle may be ignored, we obtain
(without loss of generality)
\begin{equation}
\label{eq:main:sigma:shared}
\Eus = \int_0^\infty\prod_{j=1}^n(1-F_j(\sj))\dt \rightarrow \min.
\end{equation}
This assumption is made to keep the expressions more readable.
The solution process remains the same for the general form of $u$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Necessary Conditions for an Optimal Solution for Two Processes}
\label{sec:necessary:conditions:2}
Let $A_1$ and $A_2$ be two processes 
sharing a resource. While working, one process locks the
resource, and the other is necessarily  idle. We can show
that such dependency yields a strong constraint on the behavior of the process,
allowing the building of an effective algorithm for solving the
minimization problem.

For the suspend-resume model, therefore, only two states of the system are
possible: $A_1$ is active and $A_2$ is idle ($S_1$); and $A_1$ is idle and
$A_2$ is active ($S_2$). We ignore the case where both processes are idle, since
removing such a state from the schedule will not increase the cost.
Therefore, the system continuously alternates between the two states:
$S_1\rightarrow S_2\rightarrow S_1\rightarrow S_2 \rightarrow \ldots$.
We call the time interval corresponding to each pair
$\left \langle S_1, S_2 \right \rangle$ a \emph{phase}
and denote phase $k$ by $\Phi_k$. If we denote the process switch points by 
$t_i$, the phase $\Phi_k$ corresponds to $[t_{2k-2},t_{2k}]$.
See Figure \ref{fig:states-by-time} for an illustration.
\begin{figure}[htbp] 
\begin{center}
\input{figures/states.tex}
\caption{\label{fig:states-by-time}
\small
Notations for times, states and phases for two processes
}
\end{center}
\end{figure}

By this scheme, $A_1$ is active in the intervals
$[t_0,t_1], \; [t_2, t_3], \; \ldots\; ,\; [t_{2k}, t_{2k+1}], \; \ldots\;$,
and $A_2$ is active in the intervals
$[t_1,t_2], \; [t_3, t_4], \; \ldots\; ,\; [t_{2k+1}, t_{2k+2}], \;
\ldots\;$.

Let us denote by $\zeta_{2k-1}$ the total time that $A_1$ has been active
before $t_{2k-1}$, and by $\zeta_{2k}$ the total time that $A_2$ has
been active before $t_{2k}$. By phase definition, $\zeta_{2k-1}$
and $\zeta_{2k}$ correspond to the cumulative time spent in phases $1$ to 
$k$ in states $S_1$ and $S_2$ respectively. There exists a one-to-one 
correspondence between the sequences $\zeta_i$ and $t_i$:
\begin{equation}
\zeta_{i} + \zeta_{i+1} = t_{i+1}.
\label{eq:zeta:t}
\end{equation}
Moreover, by definition of $\zeta_i$ we have
\begin{equation}
\begin{split}
&\sigma_1(t_{2k-1}) = \sigma_1(t_{2k}) = \zeta_{2k-1},\\
&\sigma_2(t_{2k}) = \sigma_2(t_{2k+1}) = \zeta_{2k}.
\end{split}
\end{equation}

Under the process switch scheme as defined above, 
the subjective schedule functions
$\sigma_1$ and $\sigma_2$ in time intervals $[t_{2k},t_{2k+1}]$ (state $S_1$
of phase $\Phi_{k+1}$) have the form
\begin{equation}
\begin{split}
& \sigma_1(t) = t - t_{2k} + \sigma_1(t_{2k}) =
t - t_{2k} + \zeta_{2k-1} = t - \zeta_{2k},\\
& \sigma_2(t) = \sigma_2(t_{2k}) = \zeta_{2k}.
\end{split}
\label{eq:zeta:sigma:1}
\end{equation}
Similarly, in the intervals $[t_{2k+1}, t_{2k+2}]$ (state $S_2$ of phase
$\Phi_{k+1}$), the subjective schedule functions are defined as
\begin{equation}
\begin{split}
& \sigma_1(t) = \sigma_1(t_{2k+1}) = \zeta_{2k+1},\\
& \sigma_2(t) = t - t_{2k+1} + \sigma_2(t_{2k+1}) =
t - t_{2k+1} + \zeta_{2k} = t - \zeta_{2k+1}.
\end{split}
\label{eq:zeta:sigma:2}
\end{equation}


Let us denote
\begin{equation*}
v(t_1, t_2) = u'_t(t_1 + t_2, t_1, t_2) + u'_{\sigma_1}(t_1 + t_2, t_1, t_2) +
u'_{\sigma_2}(t_1 + t_2, t_1, t_2)
\end{equation*}
and
\begin{equation*}
v_i(t_1, t_2) = u'_t(t_1 + t_2, t_1, t_2) + u'_{\sigma_i}(t_1 + t_2, t_1, t_2).
\end{equation*}
To provide an optimal solution for the suspend/resume model, we may
split~\eq{eq:Eus:sigma} to phases $\Phi_{k}$ and write it as
\begin{equation}
\Eus = \sum_{k=1}^\infty
\int_{t_{2k-2}}^{t_{2k}}
v(\sigma_1, \sigma_2)(1-F_1(\sigma_1))(1-F_2(\sigma_2))\dt.
\end{equation}
The last expression may be rewritten as
\begin{equation}
\begin{split}
& \Eus =\\
&\sum_{k=0}^\infty
\int_{t_{2k}}^{t_{2k+1}}
v(\sigma_1, \sigma_2)(1-F_1(\sigma_1))(1-F_2(\sigma_2))\dt +\\
&\sum_{k=0}^\infty
\int_{t_{2k+1}}^{t_{2k+2}}
v(\sigma_1, \sigma_2)(1-F_1(\sigma_1))(1-F_2(\sigma_2))\dt.
\end{split}
\label{eq:main:by-interval:shared}
\end{equation}
Using \eq{eq:zeta:sigma:1} on interval
$[t_{2k}, t_{2k+1}]$, performing substitution $x = t - \zeta_{2k}$, and
using~\eq{eq:zeta:t}, we obtain
\begin{equation}
\begin{split}
&\int_{t_{2k}}^{t_{2k+1}}
v(\sigma_1, \sigma_2) (1-F_1(\sigma_1))(1-F_2(\sigma_2))\dt =\\
&\int_{t_{2k}}^{t_{2k+1}}
v_1(t-\zeta_{2k}, \zeta_{2k})(1-F_1(t-\zeta_{2k}))(1-F_2(\zeta_{2k}))\dt =\\
&\int_{t_{2k}-\zeta_{2k}}^{t_{2k+1}-\zeta_{2k}}
v_1(x, \zeta_{2k})(1-F_1(x))(1-F_2(\zeta_{2k}))\dx=\\
&\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}
v_1(x, \zeta_{2k})(1-F_1(x))(1-F_2(\zeta_{2k}))\dx.
\end{split}
\label{eq:integral:even:shared}
\end{equation}
Similarly, for the interval $[t_{2k+1}, t_{2k+2}]$ we have
\begin{equation}
\begin{split}
&\int_{t_{2k+1}}^{t_{2k+2}}
v(\sigma_1, \sigma_2)(1-F_1(\sigma_1))(1-F_2(\sigma_2))\dt =\\
&\int_{t_{2k+1}}^{t_{2k+2}}
v_2(\zeta_{2k+1}, t - \zeta_{2k+1})
(1-F_1(\zeta_{2k+1}))(1-F_2(t-\zeta_{2k+1}))\dt =\\
&\int_{t_{2k+1}-\zeta_{2k+1}}^{t_{2k+2}-\zeta_{2k+1}}
v_2(\zeta_{2k+1}, x)(1-F_1(\zeta_{2k+1}))(1-F_2(x))\dx =\\
&\int_{\zeta_{2k}}^{\zeta_{2k+2}}
v_2(\zeta_{2k+1}, x)(1-F_1(\zeta_{2k+1}))(1-F_2(x))\dx.
\end{split}
\label{eq:integral:even:odd}
\end{equation}
Substituting~\eq{eq:integral:even:shared} and~\eq{eq:integral:even:odd}
into~\eq{eq:main:by-interval:shared}, we obtain a new form for the minimization
problem:
\begin{equation}
\begin{split}
&\Euz =\\
&\sum_{k=0}^\infty
\left[(1-F_2(\zeta_{2k}))
\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}v_1(x,\zeta_{2k})(1-F_1(x))\dx\right.+\\
&\left.(1-F_1(\zeta_{2k+1}))
\int_{\zeta_{2k}}^{\zeta_{2k+2}}v_2(\zeta_{2k+1}, x)(1-F_2(x))\dx
\right]\rightarrow\min
\label{eq:main:by-interval:zeta}
\end{split}
\end{equation}
(for the sake of generality, we assume $\zeta_{-1} = 0$).

The minimization problem~\eq{eq:main:by-interval:zeta} is equivalent to the
original problem~\eq{eq:Eus:sigma}, and the dependency
between their solutions is described by~\eq{eq:zeta:sigma:1}
and~\eq{eq:zeta:sigma:2}.
The only constraint for the new problem  follows from the fact that the
processes are alternating for non-negative periods of time:
\begin{equation}
\left\{
\begin{array}{ll}
\zeta_0 = 0 < \zeta_2 \leq \ldots \leq \zeta_{2n} \leq \ldots\\
\zeta_1 < \zeta_3 \leq \ldots \leq \zeta_{2n+1} \leq \ldots
\end{array}
\right.
\label{eq:zeta:series}
\end{equation}
The expression~\eq{eq:main:by-interval:zeta} reaches its
optimal values either when
\begin{equation}
\frac{dE_u}{d\zeta_k} = 0 \; \mbox {for} \; k = 1,\ldots, n,\ldots,
\label{eq:optimize:shared}
\end{equation}
or on the border described by~\eq{eq:zeta:series}.
However, for two processes we can, without loss of generality, ignore
the border case. Indeed, assume that $\zeta_i$ = $\zeta_{i+2}$ for some 
$i > 1$ (one of the processes skips its turn). We can construct a new 
schedule by removing $\zeta_{i+1}$ and $\zeta_{i+2}$:
\[
\zeta_1, \ldots, \zeta_{i-1}, \zeta_i, \zeta_{i+3}, \zeta_{i+4}, \zeta_{i+5},
\ldots
\]
It is easy to see that the process described by this schedule is exactly the
same process as described by the original one, but the singularity point has
been removed.

Thus, at each step  the time spent by the processes is
determined by~\eq{eq:optimize:shared}.
We can see that $\zeta_{2k}$ appears in three subsequent terms of $\Eus$:
\begin{equation*}
\begin{split}
&\ldots +
(1-F_1(\zeta_{2k-1}))
\int_{\zeta_{2k-2}}^{\zeta_{2k}}v_2(\zeta_{2k-1},x)(1-F_2(x))\dx +\\
&(1-F_2(\zeta_{2k}))
\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}v_1(x,\zeta_{2k})(1-F_1(x))\dx +\\
&(1-F_1(\zeta_{2k+1}))\int_{\zeta_{2k}}^{\zeta_{2k+2}}
v_2(\zeta_{2k+1},x)(1-F_2(x))\dx + \ldots.
\end{split}
\end{equation*}
Differentiating~\eq{eq:main:by-interval:zeta} by $\zeta_{2k}$, therefore,
yields
\begin{equation*}
\begin{split}
\frac{dE_u}{d\zeta_{2k}} & = 
v_2(\zeta_{2k-1},\zeta_{2k})(1-F_1(\zeta_{2k-1}))(1-F_2(\zeta_{2k})) -\\
&f_2(\zeta_{2k})
\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}v_1(x,\zeta_{2k})(1-F_1(x))\dx +\\
&(1-F_2(\zeta_{2k}))\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}
\frac{\partial v_1}{\partial t_2}(x,\zeta_{2k})(1-F_1(x))\dx -\\
&v_2(\zeta_{2k+1},\zeta_{2k})(1-F_1(\zeta_{2k+1}))(1-F_2(\zeta_{2k})) =\\
&(1-F_2(\zeta_{2k}))(v_2(\zeta_{2k-1},\zeta_{2k})(1-F_1(\zeta_{2k-1})) - 
                     v_2(\zeta_{2k+1},\zeta_{2k})(1-F_1(\zeta_{2k+1})) -\\
&f_2(\zeta_{2k})
\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}v_1(x,\zeta_{2k})(1-F_1(x))\dx+\\
& (1-F_2(\zeta_{2k}))\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}
\frac{\partial v_1}{\partial t_2}(x,\zeta_{2k})(1-F_1(x))\dx.
\end{split}
\end{equation*}
A similar expression can be derived by 
differentiating~\eq{eq:main:by-interval:zeta} by $\zeta_{2k+1}$.
Combining these expressions with~\eq{eq:optimize:shared} gives us the 
following theorem:
\begin{theorem}\label{th:chain:two} 
{\bf (The chain theorem for two processes)}\\
The value for $\zeta_{i+1}$ for $i\geq 2$ can be computed
for  given $\zeta_{i-1}$
and $\zeta_i$
using the formulas
\begin{equation}
\begin{split}
\frac{f_2(\zeta_{2k})}{1-F_2(\zeta_{2k})} =&
\frac{v_2(\zeta_{2k-1},\zeta_{2k})(1-F_1(\zeta_{2k-1})) - 
      v_2(\zeta_{2k+1},\zeta_{2k})(1-F_1(\zeta_{2k+1}))}
     {\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}v_1(x,\zeta_{2k})(1-F_1(x))\dx} +\\
&\frac{\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}
       \frac{\partial v_1}{\partial t_2}(x,\zeta_{2k})(1-F_1(x))\dx}
     {\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}v_1(x,\zeta_{2k})(1-F_1(x))\dx},
\quad i=2k+1,
\end{split}
\label{eq:chain:even:shared}
\end{equation}
\begin{equation}
\begin{split}
\frac{f_1(\zeta_{2k+1})}{1-F_1(\zeta_{2k+1})} =&
\frac{v_1(\zeta_{2k}, \zeta_{2k+1})(1-F_2(\zeta_{2k})) - 
      v_1(\zeta_{2k+2}, \zeta_{2k+1})(1-F_2(\zeta_{2k+2}))}
     {\int_{\zeta_{2k}}^{\zeta_{2k+2}}v_2(\zeta_{2k+1},x)(1-F_2(x))\dx} +\\
&\frac{\int_{\zeta_{2k}}^{\zeta_{2k+2}}
          \frac{\partial v_2}{\partial t_1}(\zeta_{2k+1},x)(1-F_2(x))\dx}
      {\int_{\zeta_{2k}}^{\zeta_{2k+2}}v_2(\zeta_{2k+1},x)(1-F_2(x))\dx},
\quad i=2k+2.
\end{split}
\label{eq:chain:odd:shared}
\end{equation}
\end{theorem}
\begin{corollary}\label{cor:chain:two:linear}
For the linear cost function \eq{eq:u:linear},
 the value for $\zeta_{i+1}$ for $i\geq 2$ can be computed
for  given $\zeta_{i-1}$
and $\zeta_i$
using the formulas
\begin{equation}
\frac{f_2(\zeta_{2k})}{1-F_2(\zeta_{2k})} =
\frac{F_1(\zeta_{2k+1}) - F_1(\zeta_{2k-1})}
     {\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}(1-F_1(x))\dx}, \; i=2k+1,
\label{eq:chain:even:shared:linear}
\end{equation}
\begin{equation}
\frac{f_1(\zeta_{2k+1})}{1-F_1(\zeta_{2k+1})} =
\frac{F_2(\zeta_{2k+2}) - F_2(\zeta_{2k})}
     {\int_{\zeta_{2k}}^{\zeta_{2k+2}}(1-F_2(x))\dx}, \; i=2k+2.
\label{eq:chain:odd:shared:linear}
\end{equation}
\end{corollary}
The proof follows immediately from the fact that $v_i(t_1,t_2) = a+b$.

Theorem \ref{th:chain:two} allows us to formulate an algorithm for
building an optimal solution. This algorithm is presented in the next subsection.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Optimal Solution for Two Processes: an Algorithm}
\label{sec:optimal:algorithm}
The goal of the scheduling algorithm is to minimize the
expression~\eq{eq:main:by-interval:zeta}
\begin{equation*}
\begin{split}
&\Euz =\\
&\sum_{k=0}^\infty
\left[(1-F_2(\zeta_{2k}))
\int_{\zeta_{2k-1}}^{\zeta_{2k+1}}v_1(x,\zeta_{2k})(1-F_1(x))\dx\right.+\\
&\left.(1-F_1(\zeta_{2k+1}))
\int_{\zeta_{2k}}^{\zeta_{2k+2}}v_2(\zeta_{2k+1}, x)(1-F_2(x))\dx
\right]\rightarrow\min
\end{split}
\end{equation*}
under the constraints
\begin{equation*}
\left\{
\begin{array}{ll}
\zeta_0 = 0 < \zeta_2 \leq \ldots \leq \zeta_{2n} \leq \ldots\\
\zeta_1 < \zeta_3 \leq \ldots \leq \zeta_{2n+1} \leq \ldots.
\end{array}
\right.
\end{equation*}

Assume that $A_1$ acts first ($\zeta_1 > 0$).
From Theorem~\ref{th:chain:two} we can see that
the values of $\zeta_0=0$ and $\zeta_1$ determine the set of possible values
for $\zeta_2$, the values
of $\zeta_1$ and $\zeta_2$ determine
the possible values for $\zeta_3$, and so on. 

Therefore, a non-zero value for $\zeta_1$ provides us with a tree of possible
values of $\zeta_k$. The branching factor of this tree is determined by
the number of roots of~\eq{eq:chain:even:shared}
and~\eq{eq:chain:odd:shared}.
Each possible sequence $\zeta_1, \zeta_2, \ldots$ can
be evaluated using~\eq{eq:main:by-interval:zeta}.  

For the cases where the total time is limited as discussed in
Section \ref{sec:constraints},
or where the series in that expression converge,
e.g., when each process has a finite cost of finding a solution,
the algorithm stops after a finite number of points.
In some cases, however, such as for extremely heavy-tailed
distributions, it is possible that the above series
diverge.  To ensure a finite number of iterations in such
cases, we set an upper limit on the maximal expected cost.

Another limit is added for the probability of failure. 
Since
$t_i = \zeta_{i-1} + \zeta_i$, 
the probability that both runs would
not be able to find a solution after $t_i$ is
\begin{equation*}
(1 - F_1(\zeta_{i-1}) )(1 - F_2(\zeta_i)).
\end{equation*}
Therefore, if the difference
\begin{equation*}
(1 - F_1(\zeta_{i-1})) (1 - F_2(\zeta_i)) - (1-p_1)(1-p_2)
\end{equation*}
becomes small enough, we can conclude that both runs failed
to find a solution and stop the execution.

For each value of $\zeta_1$ we can find the best sequence using one of the 
standard search algorithms, such as Branch-and-Bound. 
Let us denote the value of the best sequence for each $\zeta_1$ by
$E_u(\zeta_1)$.
Performing global optimization of $E_u(\zeta_1)$ by 
$\zeta_1$ provides us with an optimal solution for the case where $A_1$ acts
first. Note that the value of $\zeta_1$ may also be 0 ($A_2$
acts first), so we need to compare the value obtained by optimization
of $\zeta_1$ with the value obtained by optimization of $\zeta_2$ where 
$\zeta_1=0$.

The flow of the algorithm is illustrated in Figure~\ref{fig:alg:shared:2:idea},
the formal scheme is presented in Figure~\ref{fig:alg:shared:2},
and the description of the main routine (realized by the DFS Branch and Bound
method) in Figure~\ref{fig:alg:shared:2:dfsbnb}.

The algorithm considers two main branches, 
one for $A_1$ and one for $A_2$,
and they are processed by procedure $minimize\_sequence\_by\_first\_point$
(Figure~\ref{fig:alg:shared:2}). 
At each step, we initialize the array
of $\zeta$ values, and pass it, through the procedure
$build\_optimal\_sequence$, 
to the recursive procedure $dfsbnb$, which
represents the core of the algorithm (Figure~\ref{fig:alg:shared:2:dfsbnb}).

The $dfsbnb$ procedure, shown in Figure~\ref{fig:alg:shared:2:dfsbnb}, acts as
follows. It obtains as an input the array of $\zeta$ values, 
the cost involved
up to the current moment, 
and the best value reached till now. If the cost
exceeds this value, the procedure performs a 
classical Branch-and-Bound cutoff
(lines 1-2).

The inner loop (lines 4-19) corresponds to different roots of the expressions
~\eq{eq:chain:even:shared} and~\eq{eq:chain:odd:shared}. 
The new value of $\zeta$ corresponding to $\zeta_k$ is calculated by the
procedure \\$calculate\_next\_zeta$ (line 5), and it cannot exceed the
previously found root saved in $last\_zeta$ (for the first iteration,
$last\_zeta$ is initialized to $\zeta_{k-2}$), lines 3 and 8. Lines 6-7
correspond to the case where the lower bound passed to $calculate\_next\_zeta$
exceeds the maximal available time, and in this case the procedure is stopped.

After the new possible value of $\zeta$ is found, the procedure updates
the current cost (line 9), and the stopping criteria mentioned above are
validated for the new array of $\zeta$ values, which is denoted as
a concatenation of the old array and the new value of $\zeta$ (line 10).
If the task is accomplished, the cost is verified versus the best known
value (which is updated if necessary), and the procedure returns (lines 10-16).
Otherwise, $\zeta$ is temporarily added to the array of $\zeta$, and the
Branch-and-Bound procedure is called recursively for calculation $\zeta_{k+1}$.

When the whole tree is traversed (except the cutoffs), the best known
cost is returned (line 20). The corresponding array of $\zeta$ is the required
solution.


\begin{figure}[htbp] 
\begin{center}
\input{figures/algorithm-2agents.tex}
\caption{\label{fig:alg:shared:2:idea}
\small
The flow of the algorithm for constructing optimal schedules for 2
processes
}
\end{center}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\fbox{
\begin{minipage}{0.95\textwidth}
\begin{tabbing}
\TABLINE{5mm}
\PROCEDURE\ $optimize$\\
\> Input: $ F_1(t), F_2(t)$ (performance profiles).\\
\> Output: An optimal sequence and its value.\\
\> $[sequence_1, val_1] \gets minimize\_sequence\_by\_first\_point(A_1)$\\
\> $[sequence_2, val_2] \gets minimize\_sequence\_by\_first\_point(A_2)$\\
\> \IF\ $val_1 < val_2$ \THEN\ \\
\>\>  \RETURN\ $[sequence_1, val_1]$\\
\> \ELSE\ \\
\>\>  \RETURN\ $[sequence_2, val_2]$\\
\>\END \\
\END \\
\\
\PROCEDURE\ $minimize\_sequence\_by\_first\_point(process)$\\
\> $zetas[-1] \gets 0$\\
\> $zetas[0] \gets 0$\\
\> \IF\ $process = A_2$ \THEN\ \\
\>\> $zetas[1] \gets 0$\\
\>\END\ \\
\> Using one of the standard minimization methods, find $zetas$,\\
\> minimizing the value of the function $build\_optimal\_sequence(zetas)$,\\
\> and the corresponding cost.\\
\END \\
\end{tabbing}
\end{minipage}
}
\caption{\label{fig:alg:shared:2}
\small
Procedure $optimize$ builds an optimal sequence for the case when
$A_1$ starts, an optimal sequence for the case when $A_2$
starts, compares the results, and returns the best one.
Procedure $minimize\_sequence\_by\_first\_point$ returns an optimal sequence
and its value.}
\end{center}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\fbox{
\begin{minipage}{0.95\textwidth}
\begin{tabbing}
\TABLINE{5mm}
\PROCEDURE\ $build\_optimal\_sequence(zetas)$\\
\> $curr\_cost \gets calculate\_cost(zetas)$\\
\> \RETURN\ $dfsbnb(zetas, curr\_cost, MAX\_VALUE)$\\
\END \\
\> \\
\PROCEDURE\ $dfsbnb(zetas, curr\_cost, thresh)$\\
1:\>\> \IF\ ($curr\_cost \geq thresh$) \THEN\ \\	
2:\>\>\> \RETURN\ $MAX\_VALUE$\hspace{10mm} // Cutoff \\
3:\>\> $last\_value \gets zetas[length(zetas) - 2]$ \hspace{5mm}  // The previous time value \\
4:\>\> \REPEAT\ \\
5:\>\>\> $\zeta \gets calculate\_next\_zeta(zetas, last\_value)$ \\
6:\>\>\> \IF\ ($\zeta = last\_value$) \THEN\ \hspace{10mm} // Skip\\
7:\>\>\>\> \RETURN\ $thresh$\\
8:\>\>\> $last\_value \gets \zeta$\\
9:\>\>\> $delta\_cost \gets calculate\_partial\_cost(zetas, \zeta)$\\
10:\>\>\> \IF\ ($task\_accomplished([zetas\; ||\; \zeta])$) \THEN\ \hspace{10mm} // Leaf \\
11:\>\>\>\> \IF\ ($curr\_cost + delta\_cost < thresh$) \THEN\ \\
12:\>\>\>\>\> $optimal\_zetas \gets [zetas\; ||\; \zeta]$\\
13:\>\>\>\>\> $thresh \gets curr\_cost + delta\_cost$\\
14:\>\>\>\> \END\ \\
15:\>\>\>\> \RETURN\ $thresh$\\
16:\>\>\> \END\ \\
17:\>\>\> $tmp\_result \gets dfsbnb([zetas\; ||\; \zeta], curr\_cost + delta\_cost, thresh)$\\
18:\>\>\> $thresh = min(thresh, tmp\_result)$\\
19:\>\> \END\ \hspace{10mm} // repeat\\
20:\>\> \RETURN\ $thresh$\\
\END
\end{tabbing}
\end{minipage}
}
\caption{\label{fig:alg:shared:2:dfsbnb}
\small
Procedure $build\_optimal\_sequence$, given the prefix of the time
sequence, restores the optimal sequence with this prefix using the DFS Branch
and Bound search algorithm, and returns the sequence itself and its value.
$[x\; ||\; y]$ stands for concatenation $x$ and $y$.
Auxiliary functions are shown in Figure~\ref{fig:alg:aux:2}.
}
\end{center}
\end{figure}
\begin{figure}[htbp]
\begin{center}
\fbox{
\begin{minipage}{0.95\textwidth}
\begin{enumerate}
\item $calculate\_cost(zetas)$ computes the cost of the sequence (or its part)
in accordance with~\eq{eq:main:by-interval:zeta},
\item $calculate\_partial\_cost(zetas, \zeta)$ computes the additional cost
obtained by adding $\zeta$ to the sequence,
\item $calculate\_next\_zeta(zetas, last\_value)$ 
uses~\eq{eq:chain:even:shared} or~\eq{eq:chain:odd:shared} to
calculate the value of the next $\zeta$ 
that is greater than $last\_value$. If no such a solution exists, the
maximal time value is returned,
\item $task\_accomplished(zetas)$ returns $true$ when the task may be considered
to be accomplished (e.g., either maximal possible time is over, or the
probability of error is negligible, or the upper limit on the cost is exceeded).
\end{enumerate}
\end{minipage}
}
\caption{\label{fig:alg:aux:2}
\small
Auxiliary functions used in the optimal schedule algorithm}
\end{center}
\end{figure}

Figure \ref{fig:LS_BNB} shows a trace of a single Branch-and-Bound run for the
example shown in Section \ref{sec:LS} starting with the optimal value of
$\zeta_1$.  The optimal schedule derived from the the run is 679, 2393, 7815, 17184
with expected cost of 1216.49 steps.  The scheduling points are given in subjective
times.  Using objective (total) time the schedule can be written as 
679, 3072, 10208, and 25000.
In this particular run there were no Branch-and-Bound cutoffs due to the small
number of roots of~\eq{eq:chain:even:shared}
and~\eq{eq:chain:odd:shared}.
\begin{figure}[htbp] 
\begin{center}
\psfig{figure=figures/LS_BNB.eps,width=0.8\columnwidth}
\caption{\label{fig:LS_BNB}
\small
A trace of a single run of the Branch-and-Bound procedure starting with the 
optimal value of $\zeta_1$.  
}
\end{center}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Necessary Conditions for an Optimal Solution for $n$ Processes}
In this section we generalize our solution from the case of two processes
to the case of $n$ processes.

Assume that we have $n$ processes $A_1,\ldots,A_n$ using shared
resources. One of the possible ways to present a schedule is to use a sequence
\[
\langle (A_{i_1}, \Delta t_1), (A_{i_2}, \Delta t_2),
\ldots, (A_{i_j}, \Delta t_j), \ldots\rangle,
\]
where $A_{i_j}$ is the $j$-th active process, and $\Delta t_j$ is the time
allocated for this invocation of $A_{i_j}$.

To simplify the formalization of the problem, however, we use the following
alternative representation. First, we allow $\Delta t_j$ to be $0$, which
makes possible it to represent every schedule as
\[
\langle (A_1, \Delta t_1), (A_2, \Delta t_2), \ldots, (A_n, \Delta t_n),
(A_1, \Delta t_{n+1}), (A_2, \Delta t_{n+2}), \ldots, (A_n, \Delta t_{2n}),
\ldots\rangle.
\]
Therefore, the system alternates between $n$ states
$
S_1\rightarrow S_2\rightarrow \ldots \rightarrow S_n \rightarrow S_1
\rightarrow \ldots
$, where the state $S_i$ corresponds to the situation where
$A_i$ is active and the rest of the processes are idle. The time spent
in the $k$-th invocation of $S_i$ is $\Delta t_{kn + i}$.

As in the case of two processes, we call the time interval corresponding
to the sequence of states
$S_1\rightarrow S_2\rightarrow\ldots\rightarrow S_n$
a \emph{phase} and denote phase $k$ by $\Phi_k$.
We denote the process switch points of $\Phi_k$ by $t_k^1, t_k^2, \ldots,
t_k^n$, where
\begin{equation*}
t_k^i = \sum_{j=0}^{k-1} \Delta t_{nj + i}.
\end{equation*}
Process $A_i$ is active in phase $k$ in the
interval $[t_k^{i-1}, t_k^{i}]$, and the entire phase lasts from $t_k^0$
to $t_k^n$.
The corresponding scheme is shown in Figure~\ref{fig:states-by-time:n}.
\begin{figure}[htbp] 
\begin{center}
\input{figures/states-n.tex}
\caption{\label{fig:states-by-time:n}
\small
Notations for times, states and phases for $n$ processes
}
\end{center}
\end{figure}

To simplify the following discussion, we would like to allow indices $i$
in $t_k^i$ to be less than $0$ or greater than $n$. For this purpose, we denote
\begin{equation}
t_k^i = t^{i\mod n}_{k + \lfloor i/n \rfloor},
\label{eq:tki:shift}
\end{equation}
and the index of the process active in the interval $[t_k^{i-1}, t_k^i]$
we denote by $\remi$. For $i \mod n\neq 0$ we obtain $\remi = i \mod n$,
while for $i \mod n = 0$ we have $\remi = n$. Notation~\eq{eq:tki:shift}
claims that the shift by $n$ in the upper index is equivalent to the
shift by $1$ in the phase number:
\begin{equation*}
t_k^{i+n} = t_{k+1}^i.
\end{equation*}

As in the case of two processes, we denote by $\zeta_k^i$ the total
time that $A_{\remi}$ has been active up to $t_k^i$.
$\zeta_k^i$ corresponds to the cumulative time spent in
phases $1$ to $k$ in state $S_{\remi}$, and there is a one-to-one correspondence
between the sequences of $\zeta_k^i$ and $t_k^i$:
\begin{align}
&\zeta_k^i - \zeta_{k-1}^i = t_k^i - t_k^{i-1}, \label{eq:zetabyt:n}\\
&\sum_{j=0}^{n-1} \zeta_k^{i-j} = t_k^i \; \mbox{for} \; i\geq n.
\label{eq:tbyzeta:n}
\end{align}
The first equation corresponds to the fact that the time between
$t_k^{i-1}$ and $t_k^i$ is accumulated into the $\zeta$ values of
process $A_{\remi}$, while the second equation claims that at each switch
the objective time of the system is equal to the sum of the subjective times
of each process. For the sake of uniformity we also denote
\[
\zeta_{-1}^1 = \ldots = \zeta_{-1}^n = \zeta_0^0 = 0.
\]
By construction of $\zeta_k^i$ we can see, that at time interval
$[t_k^{i-1},t_k^i]$ the subjective time of process $A_j$ has the
following form:
\begin{equation}
\sigma_j(t) =
\left\{
\begin{array}{ll}
\zeta_k^j, & j = 1, \ldots, i-1,\\
(t - t_k^{i-1}) + \zeta_{k-1}^i, & j = i,\\
\zeta_{k-1}^j, & j = i+1, \ldots, n.
\end{array}
\right.
\label{eq:sigmazeta:n}
\end{equation}

The subjective time functions for a system with 3 processes are illustrated
in Figure~\ref{fig:sigmazeta:3}.
\begin{figure}[htbp] 
\begin{center}
\input{figures/scheduling3.tex}
\caption{\label{fig:sigmazeta:3}
\small
Subjective time functions for a system with 3 processes
}
\end{center}
\end{figure}

To find an optimal schedule for a system with $n$ processes,
we need to minimize the expression given by~\eq{eq:main:sigma:shared}.
The only constraints are the monotonicity
of the sequence of $\zeta$ for each process $i$:
\begin{equation}
\zeta_k^i \leq \zeta_{k+1}^i \; \mbox{for each $k, i$}.
\label{eq:zeta:series:n}
\end{equation}

Given the expressions for $\sigma_j$, we can prove the following lemma:
\begin{lemma}\label{lemma:u:nagents}
For a system of $n$ processes, the expression
for the expected cost~\eq{eq:main:sigma:shared} can be rewritten
as
\begin{equation}\label{eq:u:main:nagents}
E_u(\zeta_1, \ldots, \zeta_n, \ldots) =
\sum_{k=0}^\infty
\sum_{i=1}^{n} \prod_{j=i+1}^{i+n-1} (1-F_{\remj}(\zeta^j_{k-1}))
\int_{\zeta^i_{k-1}}^{\zeta^i_k}
(1-F_i(x))\dx.
\end{equation}
\end{lemma}
The proof is given in Appendix~\ref{proof:lemma:u:nagents}.

This lemma makes it possible to prove the chain theorem for an arbitrary
number of processes:
\begin{theorem}\label{th:chain} {\bf (The chain theorem)}
The value for $\zeta_{m+1}^{l-1}$ may either be $\zeta_m^{l-1}$, or can be
computed given the previous $2n-2$ values of $\zeta$ using  
the formula
\begin{equation}
\frac{f_l(\zeta^l_m)}{1-F_l(\zeta^l_m)} =
\frac{\displaystyle
\prod_{j=l+1}^{l+n-1}(1-F_{\remj}(\zeta^j_{m-1})) -
\prod_{j=l+1}^{l+n-1}(1-F_{\remj}(\zeta^j_m))
}
{\displaystyle
\sum_{i=l-n+1}^{l-1}\prod_{\substack{j=i+1\\ \remj\neq l}}^{i+n-1}(1-F_{\remj}
(\zeta^j_m))
\int_{\zeta^i_m}^{\zeta^i_{m+1}}(1-F_{\remi}(x))\dx
}
\label{eq:zeta:main:nagents}
\end{equation}
\end{theorem}
The proof of the theorem is given in Appendix~\ref{proof:th:chain}.

\subsection{Optimal Solution for $n$ Processes: an Algorithm}
The goal of the presented algorithm is to minimize the
expression~\eq{eq:u:main:nagents}
\begin{equation*}
E_u(\zeta_1, \ldots, \zeta_n, \ldots) =
\sum_{k=0}^\infty
\sum_{i=1}^{n} \prod_{j=i+1}^{i+n-1} (1-F_{\remj}(\zeta^j_{k-1}))
\int_{\zeta^i_{k-1}}^{\zeta^i_k}
(1-F_i(x))\dx
\end{equation*}
under the constraints
\begin{equation*}
\zeta_k^i \leq \zeta_{k+1}^i \; \mbox{for each $k, i$}.
\end{equation*}

As in the case of two processes, assume that $A_1$ acts first.
By Theorem~\ref{th:chain}, given $2n-2$ values of $\zeta$
\[
\zeta_1^0, \zeta_1^1, \ldots, \zeta_1^n, \zeta_2^1, \zeta_2^2, \zeta_2^{n-3},
\]
we can
determine all the possibilities for the value of $\zeta_2^{n-2}$
(either $\zeta_1^{n-2}$ if the process skips its turn, or one of the roots
of~\eq{eq:zeta:main:nagents}).
Given the values up to $\zeta_2^{n-2}$, we can determine the values
for $\zeta_2^{n-1}$, and so on.

The idea of the algorithm is similar to the algorithm for two processes.
The first $2n-2$ variables (including $\zeta_1^0=0$) determine the tree of 
possible values for $\zeta$. Optimization over $2n-3$ first variables,
therefore, provides us with an optimal schedule (as before, we compare the 
results for the case where the first $k < n$ variables are $0$).
The only difference from the case of two processes is that
a process may skip its turn. However, we can ignore the case when \emph{all}
the processes skip their turn, since we can remove such a loop from the 
schedule. The scheme of the algorithm is presented in 
Figure~\ref{fig:alg:shared:n},
and the description of the main routine (realized by the DFS Branch and Bound
method) is presented in Figure~\ref{fig:alg:shared:n:dfsbnb}.

\begin{figure}[htbp]
\begin{center}
\fbox{
\begin{minipage}{0.95\textwidth}
{\em Procedure $optimize$ builds $n$ optimal schedules 
(each process may start first),
compares the results, and returns the best one}
\begin{tabbing}
\TABLINE{5mm}
\PROCEDURE\ $optimize$\\
\> $best\_val \gets MAX\_VALUE$\\
\> $best\_sequence \gets \emptyset$\\
\> \LOOP\ \FOR\ $i$ \FROM\ $1$ \TO\ $n$ \DO\ \\
\>\> $[sequence, val] \gets minimize\_sequence\_by\_first\_points(i)$\\
\>\> \IF\ ($val < best\_val$) \THEN\ \\
\>\>\> $best\_val \gets val$\\
\>\>\> $best\_sequence \gets sequence$\\
\> \END\ \\
\> \RETURN\ $[best\_sequence, best\_val]$\\
\END \\
\\
// Procedure $minimize\_sequence\_by\_first\_points$ gets as a parameter \\
// the index of a process which starts, and returns an optimal \\
// sequence and its value\\
\PROCEDURE\ $minimize\_sequence\_by\_first\_points(process\_to\_start)$\\
\> \LOOP\ \FOR\ $i$ \FROM\ 0 \TO\ $n-1$\\
\>\> $zetas[-i] \gets 0$\\
\> \END\ \\
\> \LOOP\ \FOR\ $i$ \FROM\ 1 \TO\ $process\_to\_start - 1$\\
\>\> $zetas[i] \gets 0$\\
\> \END\ \\
\> Using one of the standard minimization methods, find $zetas$,\\
\> minimizing the value of the function $build\_optimal\_sequence(zetas)$.\\
\END \\
\end{tabbing}
\end{minipage}
}
\caption{\label{fig:alg:shared:n}
\small
An algorithm for finding an optimal schedule for $n$ processes.
The result contains the vector of $\zeta_i$, such that $\zeta_i = \zeta_0^i =
\zeta^{i\mod n}_{\lfloor i/n\rfloor}$.}
\end{center}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\fbox{
\begin{minipage}{0.95\textwidth}
\begin{tabbing}
\TABLINE{5mm}
\PROCEDURE\ $build\_optimal\_sequence(zetas)$\\
\> $curr\_cost \gets calculate\_cost(zetas)$\\
\> \RETURN\ $dfsbnb(zetas, curr\_cost, MAX\_VALUE, 0)$\\
\END \\
\> \\
\PROCEDURE\ $dfsbnb(zetas, curr\_cost, thresh, nskip)$\\
\> \IF\ ($curr\_cost \geq thresh$) \THEN\ \\	
\>\> \RETURN\ $MAX\_VALUE$\hspace{10mm} // Cutoff \\
\> $last\_value \gets zetas[length(zetas) - n]$
\hspace{5mm}  // The previous time value for the current process\\
\> \REPEAT\ \\
\>\> $\zeta \gets calculate\_next\_zeta(zetas, last\_value)$ \\
\>\> \IF\ ($\zeta = last\_value$) \THEN\ \hspace{10mm} // Skip\\
\>\>\> \BREAKLOOP\ \\
\>\> $last\_value \gets \zeta$\\
\>\> $delta\_cost \gets calculate\_partial\_cost(zetas, \zeta)$\\
\>\> \IF\ ($task\_accomplished([zetas\;||\;\zeta])$) \THEN\ \hspace{10mm} // Leaf \\
\>\>\> \IF\ ($curr\_cost + delta\_cost < thresh$) \THEN\ \\
\>\>\>\> $optimal\_zetas \gets [zetas\;||\;\zeta]$\\
\>\>\>\> $thresh \gets curr\_cost + delta\_cost$\\
\>\>\> \END\ \\
\>\>\> \BREAKLOOP\ \\
\>\> \END\ \\
\>\> $tmp\_result \gets dfsbnb([zetas\;||\;\zeta], curr\_cost + delta\_cost, thresh, 0)$\\
\>\> $thresh = min(thresh, tmp\_result)$\\
\> \END\ \hspace{10mm} // repeat\\
\> \IF\ ($nskip < n - 1$) \THEN\ \hspace{10mm} // Skip is possible\\
\>\> $zeta \gets zetas[length(zetas) - n]$\\
\>\> $tmp\_result \gets dfsbnb([zetas\;||\;\zeta], curr\_cost, thresh, nskip + 1)$\\
\>\> $thresh = min(thresh, tmp\_result)$\\
\> \END\ \\
\> \RETURN\ $thresh$\\
\END
\end{tabbing}
\end{minipage}
}
\caption{\label{fig:alg:shared:n:dfsbnb}
\small
Procedure $build\_optimal\_sequence$, given the prefix of time
sequence, restores the optimal sequence with this prefix using the DFS Branch
and Bound search algorithm, and returns the sequence itself and its value.
$[x\; ||\; y]$ stands for concatenation $x$ and $y$.
The auxiliary functions used are similar to their counterparts
in Figure~\ref{fig:alg:aux:2}, but deal with $n$ processes
instead of 2.}
\end{center}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Optimal Solution in the Case of Additional Constraints}
\label{sec:constraints}
Assume now that the problem has additional constraints:
the solution time is limited by $T$ and the probability of success of the $i$-th
process $p_i$ is not necessarily $1$.

It is possible to show that the expressions for the distribution function and
the expected cost have almost the same form as in the regular framework:
\begin{claim}\label{claim:br}
Let the system solution time be limited by $T$, and let $p_i$ be the 
probability
of success for the $i$-th process. Then the expressions for the goal-time
distribution and expected cost are as follows:
\begin{align}
&\Fns =
1 - \prod_{i=1}^n (1-p_i F_i(\si)) \; \text{(for $t \leq T$)},
\label{eq:Fns:sigma:br}\\
&\Eus = \int_0^{T}\left(u'_t + \sum_{i=1}^n \si' u'_{\si}\right)
\prod_{i=1}^n(1-p_iF_i(\si))\dt.
\end{align}
\end{claim}
The proof is similar to the proof of Claim~\ref{claim:suspend}.

This claim shows that all the formulas used in the previous sections
are valid for the current settings, with three differences:
\begin{enumerate}
\item We use $p_jF_j$ instead of $F_j$ and $p_jf_j$ instead of $f_j$.
\item All the integrals are from $0$ to $T$ instead of from $0$ to $\infty$.
\item All time variables are limited by $T$.
\end{enumerate}
The first two conditions may be easily incorporated into all the algorithms.
The last condition implies additional changes in the chain theorems
and the algorithms. The chain theorem for $n$ processes now becomes:
\begin{theorem}\label{th:chain:br}
The value for $\zeta_k^j$ can either be $\zeta_{k-1}^j$, or
it can be computed given the previous $2n-2$ values of $\zeta$ using  
formula~\eq{eq:zeta:main:nagents}, or it can be calculated by the formula
\begin{equation}
\zeta_k^j = T - \sum_{l=1}^{n-1} \zeta_k^{j-l}.
\label{eq:zeta:n:T}
\end{equation}
\end{theorem}
The first two alternatives are similar to Theorem~\ref{th:chain},
while the third one corresponds to the boundary condition
given by Equation~\eq{eq:tbyzeta:n}.
This third alternative adds one more branch to the DFS Branch and Bound
algorithm; the rest of the algorithm remains unchanged.

Similar changes in the algorithms are performed in the case of the maximal
allowed time $T_i$ per process. In practice, we always use this limitation,
setting $T_i$ such that the probability for $A_i$ to reach the goal 
after $T_i$,  $p_i(1 - F_i(T_i))$,  becomes negligible.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Process Scheduling by Intensity Control}
\label{sec:intensity}
 In this section we
analyze the problem of optimal scheduling for the case
of intensity control, which is
equivalent to replacing the
binary scheduling functions $\theta_i(t)$ with continuous functions
with a range between $0$ and $1$.  In this paper we 
assume a linear cost function of the form \eq{eq:u:linear}. 
We believe, however, that similar analysis is applicable 
to the setup with any differentiable $u$.

It is easy to see that all the formulas for the
distribution function
and the expected cost from Claim~\ref{claim:suspend} 
are still valid under intensity control settings.

For the linear cost function~\eq{eq:u:linear}, 
the minimization problem has the form
\begin{equation}
\Eus =\int_0^\infty\left(a + b\sum_{i=1}^n\sip\right)
\prod_{j=1}^n(1-F_j(\sj))\dt \rightarrow \min.
\label{eq:main:sigma:ab}
\end{equation}
Without loss of generality, we can assume $a + b = 1$. This leads
to the equivalent minimization problem
\begin{equation}
\Eus =\int_0^\infty\left((1-c) + c\sum_{i=1}^n\sip\right)
\prod_{j=1}^n(1-F_j(\sj))\dt \rightarrow \min,
\label{eq:main:sigma}
\end{equation}
where $c = b / (a+b)$ can be viewed as a normalized resource 
weight.
The constraints, however, are more complicated than for the 
suspend/resume model:
\begin{enumerate}
\item As before, $\sigma_i$ must be continuous, and
$\sigma_i(0) = \sigma'_i(0) = 0$
(at the beginning all the processes are idle).
\item We assume $\sigma_i$ to have a partially-continuous 
derivative $\sigma'_i$, and this derivative should lie between $0$ and $1$.
This requirement follows from the definition of intensity and the
fact that $\sigma'_i=\theta_i$: no process can work for a negative amount 
of time, and no process can work with the intensity greater than the one
allowed.
Since we consider a framework with shared resources,
and the total intensity is limited, we have an additional constraint:
the sum of all the derivatives $\sigma'_i$ at any time point cannot exceed $1$.
\end{enumerate}

Thus, this optimization problem has the following boundary conditions:
\begin{equation}
\begin{split}
&\sigma_i(0) = 0, \; \sigma'_i(0) = 0 \; \text{for $i = 1,\ldots,n$},\\
&0 \leq \sip \leq 1 \; \text{for $i = 1,\ldots,n$},\\
&0 \leq \sum_{i=1}^n \sip \leq 1.
\end{split}
\label{eq:constraint:shared}
\end{equation}

We are looking for a set of functions $\{\sigma_i\}$
that provide a solution to minimization problem~\eq{eq:main:sigma} under
constraints~\eq{eq:constraint:shared}.

Let $g(t, \sigma_1, \ldots, \sigma_n, \sigma'_1, \ldots, \sigma'_n)$
be a function under the integral sign of~\eq{eq:main:sigma}:
\begin{equation}
g(t, \sigma_1, \ldots, \sigma_n, \sigma'_1, \ldots, \sigma'_n) =
\left((1-c) + c\sum_{i=1}^n\sip\right)
\prod_{j=1}^n(1-F_j(\sj)).
\label{eq:functional:g}
\end{equation}
A traditional method for solving problems of this type is to use
the Euler-Lagrange necessary conditions:
a set of functions $\sigma_1, \ldots, \sigma_n$ provides a weak
(local) minimum to the functional
\begin{equation*}
E_u(\sigma_1, \ldots, \sigma_n) = \int_0^\infty
g(t, \sigma_1, \ldots, \sigma_n, \sigma'_1, \ldots, \sigma'_n)\dt
\end{equation*}
only if $\sigma_1, \ldots, \sigma_n$ satisfy a system of equations of the form
\begin{equation}
g'_{\sigma_k} - \frac{d}{dt}g'_{\sigma_k'} = 0.
\label{eq:euler}
\end{equation}
We can prove the following lemma:
\begin{lemma}\label{lemma:euler}
The Euler-Lagrange conditions for minimization problem~\eq{eq:main:sigma}
yield two strong invariants:
\begin{enumerate}
\item For processes $k_1$ and $k_2$ for which $\sigma_{k_1}$ and $\sigma_{k_2}$
are not on the border described by~\eq{eq:constraint:shared}, the distribution
and density functions satisfy
\begin{equation}
\frac{f_{k_1}(\sigma_{k_1})}{1-F_{k_1}(\sigma_{k_1})} =
\frac{f_{k_2}(\sigma_{k_2})}{1-F_{k_2}(\sigma_{k_2})}.
\label{eq:invariant:h}
\end{equation}
\item If the schedules of \emph{all} the processes are not on the
border described by~\eq{eq:constraint:shared}, then either
$c = 1$ or $f_k(\sigma_k) = 0$ for each $k$.
\end{enumerate}
\end{lemma}
The proof of the lemma is given in Appendix~\ref{proof:lemma:euler}.
The above lemma provides necessary conditions for a local minimum in the inner
points described by constraints~\eq{eq:constraint:shared}. These conditions,
however, are very restricting. Therefore, we look for more general conditions,
suitable for boundary points as well\footnote{Note
also that even if the conditions above hold, they do not necessarily provide 
the optimal solution. Moreover, problems in variation calculus do not 
necessarily have a minimum, since there is no analogue for the Weierstrass 
theorem for continuous functions on a closed set.}.

We start with the following lemma:
\begin{lemma}\label{lemma:max:resources}
If an optimal solution for minimization problem~\eq{eq:main:sigma}
under constraints~\eq{eq:constraint:shared} exists, then there exists an
optimal solution
$\sigma_1, \ldots, \sigma_n$, such that at each time $t$ all the resources
are consumed, i.e.,
\begin{equation}
\forall t \; \sum_{i=1}^n \sigma'_i(t) = 1.
\label{eq:all:resources}
\end{equation}
In the case where time cost is not zero ($c \neq 1$), the equality above
is a necessary condition for solution optimality.
\end{lemma}
The proof of the lemma is given in Appendix~\ref{proof:lemma:max:resources}.
\begin{corollary}\label{cor:main:shared}
Under intensity control settings, as in the case of suspend-resume settings,
minimization problem~\eq{eq:main:sigma} has the
form~\eq{eq:main:sigma:shared}, i.e.
\begin{equation*}
E_u(\sigma_1, \ldots, \sigma_n) =
\int_0^\infty \prod_{j=1}^n(1-F_j(\sj))\dt \rightarrow \min.
\end{equation*}
\end{corollary}

Lemma~\ref{lemma:max:resources} corresponds to our
intuition: if a resource is available, it should be used. 
Without loss of generality, we restrict our discussion to schedules
satisfying~\eq{eq:all:resources}, even in the case where time cost is
zero. This leads to the following invariant:
\begin{equation}
\forall t \; \sum_{i=1}^n \sigma_i(t) = t.
\label{eq:all:resources:t}
\end{equation}

Assume now that we have two $F$-equivalent processes $A_1$ and $A_2$
with density function
$f(t)$ satisfying the normal distribution law with mean value $m$. Let $t_1$
and $t_2$ be the cumulative time consumed by each of the processes at time
$t$, i.e., $\sigma_1(t) = t_1$ and $\sigma_2(t) = t_2$.
The question is, which process should be active at $t$ (or should they be
active in parallel with partial intensities)?

Without loss of generality, $t_1 < t_2$, which means that the first process is
required to cover a larger area to succeed:
$1 - F(t_1) > 1 - F(t_2)$. This supports a policy that
at time $t$ activates the second process. This policy is further
supported if $A_1$ has a lower distribution density, $f_1(t_1) < f_2(t_2)$,
as illustrated in
Figure~\ref{fig:hazard:normal:example}(a).
If, however, the first process has a higher density, as illustrated
in Figure~\ref{fig:hazard:normal:example}(b), it is not clear which of the two
processes should be activated at time $t$.
\begin{figure}[htbp]
\twofigbox{figures/normal_example1.ps}{figures/normal_example2.ps}
\begin{caption}{\label{fig:hazard:normal:example}
\small
(a) Process $A_1$ (currently at $t_1$) has lower density and
larger area to cover, and therefore is inferior. (b) Process $A_1$
has lower density, but smaller area to cover, and the decision is
unclear.
}
\end{caption}
\end{figure}
What is the optimal policy in the general case\footnote{Analysis of
normal distribution given in Section~\ref{subsec:normal} shows that
the optimal policy in the example above is to give all the resources
to process $A_2$ in both cases.}? The answer relies heavily 
on the functions that appear in~\eq{eq:invariant:h}. These functions,
described by the equation
\begin{equation}
h_k(t) = \frac{f_{k}(t)}{1-F_{k}(t)},
\label{eq:invariant:f}
\end{equation}
are known as \emph{hazard functions},
and they play a very important role in the following
theorem describing necessary conditions for optimal schedules.
\begin{theorem}\label{th:no-intensity:shared}
Let the set of functions $\{\si\}$ be a solution of
minimization problem~\eq{eq:main:sigma:shared} under
constraints~\eq{eq:constraint:shared}. Let $t_0$ be a point where
the hazard functions of all the processes $h_i(\sigma_i(t))$ are continuous,
and let $A_k$ be the process active at $t_0$ ($\sigma_k'(t_0) > 0$), such that
for any other process $A_i$ 
\begin{equation}
h_i(\sigma_i(t_0)) < h_k(\sigma_k(t_0)).
\end{equation}
Then at $t_0$ process $k$ consumes all the resources, i.e. $\sigma_k'(t_0) = 1$.
\end{theorem}
The proof of the theorem is given in
Appendix~\ref{proof:th:no-intensity:shared}.

By Theorem~\ref{th:no-intensity:shared} and
Equation~\eq{eq:invariant:h}, intensity control may only be useful when hazard
functions of at least two processes are equal. However, even in this case the
equilibrium is not always stable. Assume that within some interval $[t',t'']$
processes $A_i$ and $A_j$ are working with partial intensity, which implies
$h_i(\sigma_i(t)) = h_j(\sigma_j(t))$.
Assume now that both $h_i(t)$ and $h_j(t)$ are
monotonically increasing. If at some moment $t$ we give a
priority to one of the processes, it will obtain a higher value of the hazard
function, and will get all the subsequent resources. The only case of stable
equilibrium is when $h_i(\sigma_i(t))$ and $h_j(\sigma_j(t))$
are monotonically decreasing functions or constants.

The intuitive discussion above is formulated in the following theorem:
\begin{theorem}\label{th:h:control:increasing}
An active process will remain active and consume all resources
as long as its hazard function is monotonically increasing.
\end{theorem}
The proof is given in Appendix~\ref{proof:th:h:control:increasing}.

This theorem imply the important corollary:
\begin{corollary}\label{corollary:h:increasing}
If the hazard function of one of the processes is greater than or equal to
that of
the others at $t = 0$ and is monotonically increasing by $t$, this process
should be the only one to be activated.
\end{corollary}

We can conclude that the extension of the suspend-resume model to intensity
control in many cases does not increase the power of the model and is
beneficial only for monotonically decreasing hazard functions.
If no time cost is taken into account ($c = 1$), however, the intensity
control permits us to connect the two concepts: that of the model
with shared resources and that of the model with independent agents:
\begin{theorem}\label{th:notime:model:equivalence}
If no time cost is taken into account ($c = 1$), the model with shared 
resources under intensity control settings is equivalent to  the model
with independent processes under suspend-resume control settings.
Namely, given a suspend-resume solution for the model with independent
processes, we may reconstruct an intensity-based solution with the same cost
for the model with shared resources and vice versa.
\end{theorem}
The proof of the theorem is given in 
Appendix~\ref{proof:th:notime:model:equivalence}.


Theorem \ref{th:no-intensity:shared} claims that if the process with the
maximal value of
$h_k(\sigma_k(t))$ is active, it will take all the resources. 
Why, then, would we not always choose the process with the highest value of
$h_k(\sigma_k(t))$ to be active?
It turns out that such a strategy is not optimal. Let us consider
two processes with the
distribution densities shown in Figure~\ref{fig:hk:twoagents}(a).
The corresponding values of the hazard functions are shown in
Figure~\ref{fig:hk:twoagents}(b).
If we were using the above strategy, $A_2$ would be the only active
process.  Indeed, at time $t=0$,  $h_2(\sigma_2(0)) > h_1(\sigma_1(0))$, 
which would lead to the activation of $A_2$.  After that moment, 
$A_1$ would remain idle and its hazard function remain $0$.  This strategy
would result in an expected time of $2$.
If, on the other hand, we would have activated $A_1$ only, the result
would be an expected time of $1.5$.  Thus,
although $h_1(\sigma_1(0)) < h_2(\sigma_2(0))$, it is better to
give all the resources to $A_1$ from the beginning due to its superiority in
the future. 
\begin{figure}[htbp]
\twofigbox{figures/HK_TWOAGENTS/density.eps}{figures/HK_TWOAGENTS/hk.eps}
\begin{caption}{\label{fig:hk:twoagents}
\small
The density function and the hazard function for two processes.
Although $h_1(\sigma_1(0)) < h_2(\sigma_2(0))$, it is better to give all
the resources to $A_1$.}
\end{caption}
\end{figure}

A more elaborate example is shown in Figure~\ref{fig:hk:twoagents:second}.
It corresponds to the case of two
 processes that are not $F$-equivalent, one
of which is a linear combination of two normal distributions,
$f(t) = 0.5f_{N(0.6,0.2)}(t) + 0.5f_{N(4.0,2.0)}(t)$, where
$f_{N(\mu,\sigma)}(t)$ is the distribution density of normal distribution
with mean value $\mu$ and standard deviation $\sigma$, and the second process
is uniformly distributed in $[1.5,2.5]$.  Activating $A_1$ only results in
$0.5 \times 0.6 + 0.5 \times 4.0 = 2.3$, activating $A_2$ only results in
an expected time of $2.0$, while activating $A_1$ for time
$1.2$ followed by activating $A_2$ results in (approximately)
 $0.6 \times 0.5 + (1.2 + 2.0) \times 0.5 = 1.9$. 
The best solution is, therefore,
 to start the execution by activating $A_1$,
and at some point $t'$ transfer the control to $A_2$.
In this case we interrupt an active process with  a greater value of hazard
function,  preferring an idle process with a zero value of hazard function
(since $h_1(\sigma_1(t')) > h_2(\sigma_2(t')) = 0$).
\begin{figure}[htbp]
\twofigbox{figures/HK_TWOAGENTS/density2.eps}{figures/HK_TWOAGENTS/hk2.eps}
\begin{caption}{\label{fig:hk:twoagents:second}
\small
The density function and the hazard function for two processes.
The best solution is to start with $A_1$, and at some point interrupt
it in favor of $A_2$, although the latter has a zero hazard function.
}
\end{caption}
\end{figure}

These examples show that a straightforward use of hazard functions
for building optimal schedules can be very problematic.
However, since the suspend-resume model is a specific case of the
intensity control model, the hazard functions still may be useful
for understanding the behavior of optimal schedules, and this is used
in the next section.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Optimal Scheduling for Standard Distributions}
\label{sec:standard:distributions}
In this section we present the results of the optimal scheduling strategy
for a system of processes whose performance profiles meet one of the well-known
distributions: uniform, exponential, normal and lognormal. Then
we show the results for processes with bimodal and multimodal distribution
functions.

We have implemented three scheduling policies for two agents:
\begin{enumerate}
\item {\bf Sequential strategy}, which schedules the processes one after
another, initiating the second process when the probability that the first one
will find a solution becomes negligible. For
 processes that are not $F$-equivalent,
we choose the best order of process invocation.
\item {\bf Simultaneous strategy}, which simulates a simultaneous execution
of both processes.
\item {\bf Optimal strategy}, which is an implementation of the algorithm
described in Section~\ref{sec:optimal:algorithm}.
\end{enumerate}
In the rest of this section we compare these three strategies,
when no deadline is given, and the processes are stopped when the probability
that they can still find a solution becomes negligible.

Our goal is to compare different scheduling strategies and not to analyze
the behavior of the processes. Absolute quantitative measurements, such as
average cost, are very process dependent, and therefore are
not appropriate for scheduling strategy evaluation.
We therefore would like to normalize the results of the application of 
different scheduling methods to minimize the effect of the 
process behavior.
In the case of $F$-equivalent processes, a good candidate
for the normalization coefficient is the expected time of the individual
process.
For
 processes that are not $F$-equivalent,
however, the decision is not straightforward,
and therefore we use the results of the sequential strategy as the normalization
factor.

We define the \emph{relative quality} $q_{ref}(S)$ of strategy
$S$ with respect to strategy $S_{ref}$ as 
\begin{equation}
q_{ref}(S) = 1 - \frac{\bar{u}(S)}{\bar{u}(S_{ref})},
\end{equation}
where $\bar{u}(S)$  is the average cost of strategy $S$.
This measurement corresponds to the gain (maybe negative) of strategy $S$
relative to the reference strategy.
In this section we use the sequential strategy as our reference strategy.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Uniform Distribution}
Assume that the goal-time distribution of the processes
meets the uniform law over the interval $[t_0,T]$, i.e.,
has distribution functions 
\begin{equation}
F(t) = \left\{\begin{array}{ll}
0 & \mbox{if $t < t_{0}$,}\\
(t-t_{0})/(T-t_{0}) & \mbox{if $t \in [t_{0}, T]$,}\\
1 & \mbox{if $t > T$}
\end{array}
\right.
\end{equation}
and density functions
\begin{equation}
f(t) = \left\{\begin{array}{ll}
0 & \mbox{if $t \not\in [t_{0}, T]$,}\\
1/(T-t_{0}) & \mbox{if $t \in [t_{0}, T]$.}
\end{array}
\right.
\label{eq:uniform}
\end{equation}
The density function of a process uniformly distributed in $[0,1]$
is shown in Figure~\ref{fig:uniform:h}(a).

The hazard function of the uniform distribution has the form
\begin{equation}
h(t) = \left\{\begin{array}{ll}
0 & \mbox{if $t < t_{0}$,}\\
\dfrac{1/(T-t_{0})}{1 - (t-t_{0})/(T-t_{0})} = \dfrac{1}{T-t} &
\mbox{if $t \in [t_{0}, T]$,}
\end{array}
\right.
\end{equation}
which is a monotonically increasing function.
By Corollary~\ref{corollary:h:increasing}, only one process
will be active, and the optimal strategy should be equivalent to the
sequential strategy.
 If the processes are not $F$-equivalent, 
the problem can be solved
by choosing the process with the minimal expected time.


A more interesting setup involves a uniformly distributed process
that is not guaranteed to find a solution.  This case
corresponds to a probability of success $p$ that is less than 1.
As it was claimed in Section \ref{sec:constraints}, the corresponding distribution
and density function should be multiplied by $p$.
As a result, 
the hazard function becomes
\begin{equation}
h(t) = \left\{\begin{array}{ll}
0 & \mbox{if $t < t_{0}$,}\\
\dfrac{p}{(T - t_{0}) - p(t - t_{0})} &
\mbox{if $t \in [t_{0}, T]$.}
\end{array}
\right.
\end{equation}
This function is still monotonically increasing by $t$, and the
conclusions remain the same. 
The graphs for hazard functions of processes uniformly distributed
in $[0,1]$ with probability of success of $0.5$, $0.8$ and
$1$ are shown in Figure~\ref{fig:uniform:h}(b).
\begin{figure}[htbp] 
\twofigbox{figures/UNIFORM/f.eps}{figures/UNIFORM/h.eps}
\caption{\label{fig:uniform:h}
\small (a) The density function of a process, uniformly distributed
in $[0,1]$, (b) hazard functions for processes uniformly distributed in $[0,1]$
with probability of success of $0.5$, $0.8$ and $1$.
}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Exponential Distribution}
\label{sec:exponential}
The exponential distribution is described by the density function
\begin{equation}
f(t) = \left\{\begin{array}{ll}
0 & \mbox{if $t\leq 0$}\\
\lambda e^{-\lambda t} & \mbox{if $t > 0$},
\end{array}
\right.
\label{eq:exp:1}
\end{equation}
and the distribution function has the form
\begin{equation}
F(t) = \left\{\begin{array}{ll}
0 & \mbox{if $t \leq 0$}\\
1 - e^{-\lambda t} & \mbox{if $t > 0$}.
\end{array}
\right.
\label{eq:exp:2}
\end{equation}
Substituting these expressions into~\eq{eq:main:sigma:shared} gives
\begin{equation*}
\Eus = \int_0^\infty\prod_{j=1}^n(1-F_j(\sj))\dt =
\int_0^\infty e^{-\sum_{j=1}^n \lambda_j\sigma_j(t)}\dt.
\end{equation*}
For a system with $F$-equivalent processes, by Lemma~\ref{lemma:max:resources}
\begin{equation*}
\sum_{j=1}^n \lambda_j\sigma_j(t) = \lambda\sum_{j=1}^n\sigma_j(t) =
\lambda t,
\end{equation*}
and therefore
\begin{equation*}
\Eus = \int_0^\infty e^{-\lambda t}\dt = \frac{1}{\lambda}.
\end{equation*}
Thus, for a system with $F$-equivalent processes all the schedules are
equivalent.
This interesting fact is reflected also in the behavior
of the hazard function, which is constant:
\begin{equation*}
h(t) \equiv \lambda.
\end{equation*}

However, if the probability of success is smaller than $1$, the hazard function
becomes a monotonically decreasing function:
\begin{equation*}
h(t) = \frac{p\lambda e^{-\lambda t}}{1-p(1-e^{-\lambda t})} =
\frac{p\lambda}{p + (1-p)e^{\lambda t}}.
\end{equation*}
Such processes
should work simultaneously (with identical intensities for $F$-equivalent
processes, and with intensities maintaining the equilibrium of hazard functions
otherwise),
since each process which has been idle for a while has  an advantage over its
working teammate.

Figure~\ref{fig:exponential:h}(a) shows the density function of 
an exponentially distributed process with $\lambda = 1$.
The graphs for the hazard functions of processes exponentially distributed
with $\lambda = 1$ and probability of success of $0.5$, $0.8$ and
$1$ are shown in Figure~\ref{fig:exponential:h}(b).
\begin{figure}[htbp] 
\twofigbox{figures/EXPONENTIAL/f.eps}{figures/EXPONENTIAL/h.eps}
\caption{\label{fig:exponential:h}
\small (a) The density function of a process, exponentially distributed
with $\lambda = 1$, (b) hazard functions for processes exponentially
distributed with $\lambda=1$ and probability of success of $0.5$, $0.8$ and $1$.
}
\end{figure}

Let us consider a somewhat more elaborate example, involving
processes that are not $F$-equivalent. 
Assume that we have two learning
systems, both
with an exponential-like performance profile typical of such
systems. We also assume that one of the systems requires a delay for 
preprocessing but works faster.
Thus, we assume that the first system has a distribution density
$f_1(t) = \lambda_1 e^{-\lambda_1 t}$, and  the second one
has a density $f_2(t) = \lambda_2 e^{-\lambda_2 (t - t_2)}$, such that
$\lambda_1 < \lambda_2$ (the second is faster), and $t_2 > 0$ (it also
has a delay). Assume that both learning systems are deterministic over a given
set of examples, and that they may fail to learn the concept with
the same probability of $1 - p = 0.5$. The graphs for the density and
hazard functions of the two systems are shown in
Figure~\ref{fig:exponential:example}.
\begin{figure}[htbp] 
\twofigbox{figures/EXPONENTIAL/f_example.eps}{figures/EXPONENTIAL/h_example.eps}
\caption{\label{fig:exponential:example}
\small (a) Density and (b) hazard functions for two exponentially distributed
systems, with different values of $\lambda$ and time shift.
}
\end{figure}

We applied the optimal scheduling algorithm of
Section~\ref{sec:optimal:algorithm} for the values
$\lambda_1 = 3$, $\lambda_2 = 10$, and $t_2 = 5$.
The optimal schedule is to activate the first system for $1.15136$ time units,
then
(if it found no solution) to activate the second system for $5.77652$ time units.
Then the first system will run for additional $3.22276$ time units, and finally
the second system will run for $0.53572$ time units. If at this point no
solution has been found, both systems have failed with a probability of
$1-10^{-6}$ each.

Figure~\ref{fig:learning:systems}(a) shows the
relative quality of the simultaneous and optimal scheduling strategies
as a function of $t_2$ for $p = 0.8$ (for $10000$ simulated examples).
For large values of $t_2$ the benefit of switching from the first algorithm
to the second decreases, and this is reflected in the relative quality of the
optimal strategy. The simultaneous strategy, as we can see, is beneficial 
only for relatively small values of $t_2$.

Figure~\ref{fig:learning:systems}(b) reflects the
behavior of the strategies for a fixed value of $t_2 = 5.0$ as a function
of probability of success $p$. The simultaneous strategy is inferior, and
its quality decreases while $p$ increases. Indeed, when the probability of
success is $1$, running the second algorithm and the first one
simultaneously will be a waste of time. On the other hand, the optimal strategy
has a positive benefit, which means that the resulting schedules are
not trivial.
\begin{figure}[htbp] 
\twofigbox{figures/EXPONENTIAL_PEAKS/q_shift_running.p_0.80.eps}
          {figures/EXPONENTIAL_PEAKS/q_shift_05.p_running.eps}
\caption{\label{fig:learning:systems}
\small
Learning systems: Relative quality of optimal and simultaneous
scheduling strategies
(a) as a function of $t_2$ for fixed $p = 0.8$, and (b)
as a function of $p$ for fixed $t_2 = 5$.
}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Normal Distribution}\label{subsec:normal}
The normal distribution with  mean value $m$ and deviation $\sigma$ is
described by the density function
\begin{equation}
f(t) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(t-m)^2}{2\sigma^2}},
\label{eq:norm:1}
\end{equation}
and its distribution function is
\begin{equation}
F(t) =
\frac{1}{\sqrt{2\pi}\sigma}\int_{-\infty}^t e^{-\frac{(x-m)^2}{2\sigma^2}}dx.
\label{eq:norm:2}
\end{equation}
Since we use $t_0 = 0$,
we should have used a truncated normal distribution with a distribution density
\[
\frac{1}{(1-\mu)}\cdot
\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(t-m)^2}{2\sigma^2}},
\]
and a distribution function 
\[
\frac{1}{1-\mu}\cdot\left[
\frac{1}{\sqrt{2\pi}\sigma}\int_{-\infty}^t e^{-\frac{(x-m)^2}{2\sigma^2}}dx - \mu\right],
\]
where 
\[
\mu = \frac{1}{\sqrt{2\pi}\sigma}\int_{-\infty}^0 e^{-\frac{(x-m)^2}{2\sigma^2}}dx,
\]
but if $m$ is large enough, $\mu$ may be considered to be $0$.
The density function of a normally distributed process with $m = 5$ and
$\sigma = 1$ is shown in Figure~\ref{fig:normal:h}(a).

The hazard function of a normal distribution is monotonically increasing,
which leads to the same conclusions as for a uniform distribution.
However, a probability of success of less than $1$ completely changes
the behavior of the hazard function: after some point, it 
starts to
decrease. The graphs for hazard functions of processes normally distributed
with a mean value of $5$, standard deviation of $1$ and probabilities of
success of $0.5$, $0.8$ and $1$ are shown in Figure~\ref{fig:normal:h}(b).
\begin{figure}[htbp] 
\twofigbox{figures/NORMAL/f.eps}{figures/NORMAL/h.eps}
\caption{\label{fig:normal:h}
\small (a) The density function of a normally distributed process, with $m = 5$
and $\sigma = 1$, (b) hazard functions for normally distributed processes 
with $m = 5$ and $\sigma = 1$,
with the probabilities of success of $0.5$, $0.8$ and $1$.
}
\end{figure}

As in the previous example, we now consider a case of two
 processes that are not $F$-equivalent,
running with the same deviation $\sigma = 1$ and
the same probability of success $p$. The first process is assumed to
have $m_1 = 1$, while the second process is started with some delay $\Delta m$.
The relative quality for $10000$ simulated examples is shown in 
Figure~\ref{fig:normal:systems}.
Figure~\ref{fig:normal:systems}(a) shows  the
relative quality as a function of $\Delta m$ for $p = 0.8$;
Figure~\ref{fig:normal:systems}(b) shows  the relative quality
as a function of $p$
for $\Delta m = 2$. Unlike exponential
distribution, the gain for this example for the optimal strategy is 
rather small.
\begin{figure}[htbp] 
\twofigbox{figures/NORMAL_PEAKS/q_dmean_running.p_0.80.eps}
          {figures/NORMAL_PEAKS/q_dmean_02.p_running.eps}
\caption{\label{fig:normal:systems}
\small
Normal distribution: relative quality (a) as a function of $\Delta m$ for fixed
$p = 0.8$, and (b) as a function of $p$ for fixed $\Delta m = 2$.
}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Lognormal Distribution}
The random variable $X$ is lognormally distributed, if $\ln X$ is normally
distributed. The density function and the distribution function with
the corresponding parameters $m$ and $\sigma$ can be written as
\begin{gather}
f(t) = \frac{1}{t\sqrt{2\pi}\sigma}e^{-\frac{(\log(t)-m)^2}{2\sigma^2}},
\label{eq:lognorm:1}
\\
F(t) =
\frac{1}{\sqrt{2\pi}\sigma}\int_{-\infty}^{\log(t)} e^{-\frac{(x-m)^2}{2\sigma^2}}dx.
\label{eq:lognorm:2}
\end{gather}
Lognormal distribution plays a significant role in AI applications since
in many cases search time is distributed under the lognormal law.
The  density function of the lognormal distribution with
mean value of $\log(5.0)$ and standard deviation of $1.0$ is shown in
Figure~\ref{fig:lognormal:fh}(a), and the hazard functions for
different values of $p$ are shown in 
Figure~\ref{fig:lognormal:fh}(b).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[htbp] 
\twofigbox{figures/LOGNORMAL/f.eps}{figures/LOGNORMAL/h.eps}
\caption{\label{fig:lognormal:fh}
\small (a) Density function for lognormal distribution with mean value of
$\log(5.0)$ and standard deviation of $1.0$ and 
(b) hazard functions for lognormally distributed processes
with mean value of $\log(5.0)$,
standard deviation of $1$, and the probabilities of success of $0.5$, $0.8$
and $1$.
}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Let us consider a simulated experiment similar to its analogue for normal
distribution. We consider two
processes that are not $F$-equivalent,
with the parameters
$\sigma = 1$ and the same probability of success $p$. The first process is
assumed to have $m_1 = 1$, while the second process is started with some delay,
such that $m_2 - m_1 = \Delta m > 0$.
The relative quality for $10000$ simulated 
examples is shown in Figure~\ref{fig:lognormal:systems}.
Figure~\ref{fig:lognormal:systems}(a) shows the 
relative quality as a function of $\Delta m$ for $p = 0.8$;
Figure~\ref{fig:lognormal:systems}(b) shows the relative quality
as a function of $p$
for $\Delta m = 2$. The graphs show that for small values of $\Delta m$
both the optimal and the simultaneous strategy have a significant benefit
over the sequential one. However, for larger values, the performance
of the optimal strategy approaches the performance of the sequential strategy,
while the simultaneous strategy becomes inferior.
\begin{figure}[htbp] 
\twofigbox{figures/LOGNORMAL_PEAKS/q_dmean_running.p_0.80.eps}
          {figures/LOGNORMAL_PEAKS/q_dmean_2.0.p_running.eps}
\caption{\label{fig:lognormal:systems}
\small
Lognormal distribution: relative quality (a) as a function of $\Delta m$ for
fixed $p = 0.8$, and (b) as a function of $p$ for fixed $\Delta m = 2$.
}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Bimodal and Multimodal Density Functions}
Experiments show that in the case of $F$-equivalent processes with a unimodal
distribution function, the sequential strategy is often optimal.
In this section we consider less trivial distributions.

Assume first that we have a non-deterministic algorithm with a performance
profile expressed by a linear combination of two normal distributions with
the same deviation:
\begin{equation*}
f(t) = 0.5 f_{N(\mu_1, \sigma)} + 0.5 f_{N(\mu_2, \sigma)}.
\end{equation*}
An example of the density and hazard functions of such distributions with
$\mu_1 = 2, \mu_2 = 5$, and $\sigma = 0.5$ is given in
Figure~\ref{fig:bimodal:fh}.
\begin{figure}[htbp] 
\twofigbox{figures/BIMODAL/f.eps}{figures/BIMODAL/h.eps}
\caption{\label{fig:bimodal:fh}
\small (a) Density function and (b) hazard function for a process distributed
according to the density function
$f(t) = 0.5 f_{N(2, 0.5)} + 0.5 f_{N(5, 0.5)}$ with the 
probability of success of $p = 0.8$.
}
\end{figure}

Assume that we invoke two runs of this algorithm with
fixed values of $\mu_1 = 2$, $\sigma = 0.5$, and $p = 0.8$,
 and the free variable $\mu_2$. 
Figure~\ref{fig:bimodal} shows how the relative quality of
the scheduling strategies is influenced by the distance between the peaks,
$\mu_2 - \mu_1$. The results correspond to the intuitive claim that
the larger distance between the peaks, the more attractive the optimal 
and the simultaneous strategies become.
\begin{figure}[htbp] 
\begin{center}
\psfig{figure=figures/BIMODAL_PEAKS/q_mean2_running.p_0.80.eps,width=3in}
\caption{\label{fig:bimodal}
\small
Bimodal distribution: relative quality as a function of the distance between
the peaks.
}
\end{center}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Now let us see how the number of peaks of the density function affects
the scheduling quality. We consider a case of partial uniform
distribution, where the density is distributed over $k$ identical
peaks of length $1$ placed symmetrically in the time interval from 
$0$ to $100$. (Thus, the density function will be equal to $1/k$ when $t$
belongs to one of such peaks, and $0$ otherwise.) In this experiment we
have chosen $p = 1$.

Figure~\ref{fig:multimodal} shows the relative quality of the system
as a function of $k$, obtained for $10000$ randomly generated examples.
We can see from the results, that the simultaneous strategy is inferior,
due to the ``valleys'' in the distribution function.
The optimal strategy returns schedules where the processes switch after 
each peak, but the relative quality of the schedules decreases 
as the number of peaks increases.
\begin{figure}[htbp] 
\begin{center}
\psfig{figure=figures/MULTIMODAL_PEAKS/q_peaks_running.p_1.00.eps,width=3in}
\caption{\label{fig:multimodal}
\small
Multimodal distribution: relative quality as a function of the number of peaks.
}
\end{center}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Experiments: Using Optimal Scheduling for the Latin Square Problem}
\label{sec:experiments}

To test the performance of our algorithm in a realistic domain, we
 applied it to the Latin Square problem described in Section \ref{sec:LS}.
We assume that we are given a Latin Square problem with two initial
configurations, and a fully deterministic algorithm with distribution
function and distribution density shown in Figure~\ref{fig:LS:Ff}.

We compare the performance of the schedule produced by our algorithm
to the performance of the sequential and
simultaneous  strategies
described in Section~\ref{sec:standard:distributions}. In addition, we test
a schedule which runs the processes one after another, allowing
a single switch at the \emph{optimal} point (an analogue of the restart
technique for two processes). We refer to
this schedule as a single-point restart schedule.

Note that
the case of two initial configurations corresponds to the case of two
processes in our framework. In general, we could think of a \emph{set}
of $n$ initial configurations that would correspond to $n$ processes.
For sufficiently large $n$, the restart strategy where each restart
starts with a different initial configuration, 
becomes close to optimal.


Our experiments were performed for different values of $N$, with
$10\%$ of the square pre-colored.  The performance profile
was induced based on a run of $50,000$ instances, and the remaining $50,000$
instances were used as $25,000$ testing pairs.
All the schedules were applied with a fixed deadline $T$,
which corresponds to the maximal allowed number of generated nodes.

Since the results of the sequential strategy in this type
of problems are much worse than the results of other strategies for 
sufficiently large
values of $T$, we instead used the simultaneous 
strategy as the reference
in the relative quality measure.

\begin{figure}[htbp] 
\begin{center}
\psfig{figure=figures/LATIN_SQUARE/q_out.1000.res.20.0.1.100000.eps}
\caption{\label{fig:experiment:ls}
\small Relative quality as a function of maximal allowed time $T$
}
\end{center}
\end{figure}

Figure~\ref{fig:experiment:ls} shows how maximal available time $T$
(the $x$ axis) influences the
quality of the schedules (the $y$ axis), where the simultaneous strategy
has been used as a reference.

For small values of $T$, both single-point restart and the optimal strategy
have about a $25\%$ gain over the simultaneous strategy, since they produce
schedules which are close to the sequential one. However, when available
time $T$ increases, the benefit of parallelization becomes more significant,
and the simultaneous strategy overcomes the single-point restart strategy.
The relative quality of the optimal schedule also decreases when $T$
increases, since the resulting schedule contains more switches between
the two problem instances being solved.

\begin{figure}[htbp] 
\begin{center}
\psfig{figure=figures/LATIN_SQUARE/q_all.25000.eps}
\caption{\label{fig:experiment:ls:byN}
\small Relative quality as a function of the size of the Latin Square
}
\end{center}
\end{figure}

Figure~\ref{fig:experiment:ls:byN} illustrates how the optimal
and single-point restart schedules relate to the simultaneous schedule
for different size Latin Squares (given $T = 25,000$). The initial
gain of both strategies is about $50\%$. However, for the problems with $N=20$
the single-point restart strategy becomes worse than the simultaneous one.
For larger sizes the probability of solving the Latin Square problem 
with a time limit of $25,000$ steps becomes smaller and smaller, 
and the benefit of the optimal strategy also approaches zero.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Combining Restart and Scheduling Policies}
\label{sec:LS:restarts}
\myfullciteauthor{Luby \emph{et al.}}{Luby:1993:OSL} showed
that the
restart strategy is optimal if an infinite number of identical
runs are available.
When this number 
 is limited, the restart strategy is not optimal. 
 Sometimes, however, we have a mixed situation. Assume that 
we have two initial states, a \emph{non-deterministic} algorithm,
and a linear time cost.
On one hand, we can perform restarts of a run corresponding
 to one of the initial states. 
 On the other hand, we can switch between the runs corresponding to
 the two initial states. 
What would be an optimal policy in this case?

The expected time of a run based on a single initial state is
 \begin{equation}
E(t^*) = \frac{1}{F(t^*)}\int_0^{t^*} (1-F(t))\dt,
\label{eq:restart:optimal:t}
\end{equation}
where  $t^*$ is the restart point and
  $F(t)$ is the distribution function.
This formula is obtained by a simple summation of the geometric series
with coefficient $1-F(t^*)$, and is a continuous form of
the formula given by~\myfullciteauthor{Luby \emph{et al.}}{Luby:1993:OSL}.
Minimization of \eq{eq:restart:optimal:t} by $t^*$ 
  gives us the optimal restart point.

Assume first that the sequence of restarts on a single initial state
is a process interruptible only at the restart points.
Since the probability of failure of $i$ successive restarts 
is $(1-F(t^*))^i$,
this process is exponentially distributed.
Thus, the problem is reduced to scheduling of two exponentially
distributed processes.
According to the analysis in Section~\ref{sec:exponential},
all schedules are equivalent if the problems corresponding
to the two initial states are solvable.
Otherwise, the optimal policy is to alternate between the
two processes at each restart point.

A more interesting case is when we allow rescheduling
at any time point. In general, it is not beneficial to 
switch between the processes in non-restart points 
(otherwise these rescheduling points would have been
chosen for restart).  Such rescheduling, however, 
can be beneficial if the cost associated with restarts
is higher than the rescheduling cost\footnote{
An example for such setup is robotic search, 
where returning the robot to the initial
position is more expensive than suspending and resuming 
the robot.}.


Let us assume that each restart has a constant cost $C$. 
Similarly to~\eq{eq:restart:optimal:t}, we can 
write the expected cost of a policy performing restarts
at point $t^{**}$ as
\begin{equation}
E(t^{**}) = \frac{1}{F(t^{**})}\int_0^{t^{**}} (1-F(t))\dt + 
\frac{1-F(t^{**})}{F(t^{**})^2}C,
\label{eq:restart:optimal:tC}
\end{equation}
where the second term corresponds to the series
\begin{equation*}
0 + C(1 - F(t^{**})) + 2C(1-F(t^{**}))^2 + \ldots
\end{equation*}
Let $t^{**}$ and $t^{*}$ be the optimal restart points for the setups 
with and without associated costs respectively. 
$t^{**}$ should be greater than  $t^{*}$ due to the restart cost.

Let us consider the following schedule: the first
process runs for $t^*$, then the second process
runs for $t^*$, then the first process runs (with no restart)
for additional $t^{**} - t^*$, then the second 
process runs for additional $t^{**}-t^*$.  Then
the first process restarts and runs for $t^*$ and so
forth.

Let us compare the expected time of such schedule with the time
of the pure restart policy, where 
the first
process runs for $t^{**}$, then the second process
runs for $t^{**}$, then
the first process restarts and runs for $t^{**}$ and so
forth.

Similarly to~\eq{eq:main:by-interval:zeta},
the expected time of the first schedule in the interval
$[0,2t^{**}]$ can be 
written as
\begin{equation*}
\begin{split}
&E_{sched} = \int_0^{t^*}(1-F(t))\dt + (1-F(t^*))\int_{0}^{t^*}(1-F(t))\dt +\\
&(1-F(t^*))\int_{t^*}^{t^{**}}(1-F(t))\dt + 
(1-F(t^{**}))\int_{t^*}^{t^{**}}(1-F(t))\dt.
\end{split}
\end{equation*}
On the other hand, the expected time of the second schedule in the 
same interval is
\begin{equation*}
\begin{split}
E_{simple} = &\int_0^{t^{**}}(1-F(t))\dt + 
(1-F(t^{**}))\int_{0}^{t^{**}}(1-F(t))\dt = \\
&(2-F(t^{**}))\int_{0}^{t^{**}}(1-F(t))\dt .
\end{split}
\end{equation*}
$E_{sched}$ can be rewritten as
\begin{equation*}
\begin{split}
&E_{sched} = \int_0^{t^*}(1-F(t))\dt + 
(1-F(t^*))\int_{0}^{t^{**}}(1-F(t))\dt +\\
&(1-F(t^{**}))\int_0^{t^{**}}(1-F(t))\dt -
(1-F(t^{**}))\int_0^{t^{*}}(1-F(t))\dt=\\
& F(t^{**})\int_0^{t^*}(1-F(t))\dt +
(2 - F(t^*) - F(t^{**}))\int_{0}^{t^{**}}(1-F(t))\dt =\\
& F(t^{**})\int_0^{t^*}(1-F(t))\dt -
  F(t^{*})\int_0^{t^{**}}(1-F(t))\dt + E_{simple}.
\end{split}
\end{equation*}
Thus, we obtain
\begin{equation*}
\begin{split}
&E_{simple} - E_{sched} = 
F(t^{*})\int_0^{t^{**}}(1-F(t))\dt -
F(t^{**})\int_0^{t^*}(1-F(t))\dt =\\
& F(t^{*})F(t^{**})\left(
\frac{1}{F(t^{**})}\int_0^{t^{**}}(1-F(t))\dt -
\frac{1}{F(t^{*})}\int_0^{t^*}(1-F(t))\dt\right),
\end{split}
\end{equation*}
and since $t^*$ provides minimum for~\eq{eq:restart:optimal:t},
the last expression is positive, which means that scheduling
improves a simple restart policy.

Note, that we do not claim that the proposed scheduling policy is 
optimal --
our example just shows that the pure restart strategy is not optimal.
There
should be an optimal combination interleaving restarts on the global
level and scheduling on the local level, but finding this combination
is left for future research.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Conclusions}
In this work we present an algorithm for optimal scheduling
of anytime algorithms with shared resources.
We first introduce a formal framework for representing and analyzing
scheduling strategies.  We begin by analyzing the case where the only
allowed scheduling operations are suspending and resuming processes.
We prove necessary conditions for schedule optimality and present
an algorithm for building optimal schedules that is based on those conditions.
We then analyze the more general case where the scheduler can increase
or decrease the intensity of the scheduled processes.  We prove
necessary conditions and show that intensity control is only rarely 
needed.  We then analyze, theoretically and empirically, the behavior
of our scheduling algorithm for various distribution types.  Finally,
we present empirical results of applying our scheduling algorithm
to the Latin Square problem.  

The results show that the optimal strategy indeed outperforms other
scheduling strategies.   For lognormal distribution, we showed
an improvement of more than $50\%$ over the naive sequential
strategy. In general, our algorithm is particularly beneficial
for heavy-tailed distributions, but even for exponential 
distribution we show a benefit of more than $35\%$.

In some cases, however, simple scheduling strategies yield results
 similar to those obtained by our algorithm.
For example, the optimal schedule for uniform distribution is to
apply one of the processes with no switch.  
When the probability to succeed within
the given time limit approaches 1,  this simple scheduling strategy 
also becomes close to optimal, at least for unimodal distributions
with no strong skew towards zero.  On the other hand, when
the probability of success approaches zero, another simple strategy
that applies the processes simultaneously becomes close to optimal.

Such a behavior meets the intuition. For heavy-tailed distributions,
switching between the runs is promising because the chance to be on
a bad trajectory is high enough. The same is correct for distributions
with low probability of success. However, if the probability
to be on a bad trajectory is too high, the best strategy is to switch
between the runs as fast as possible, which is equivalent to the
simultaneous strategy. On the other hand, if the distribution is too skewed
to the right, often there is no sense to switch between the runs, since
the new run should pay a high penalty before it reaches the ``promising''
distribution area. In general,
when the user is certain that the particular application
falls under one of the categories above, 
the cost of calculating the optimal
schedule can be saved.


The high complexity of computation is one of the 
 potential weaknesses of the presented algorithm.
This complexity can be represented as a multiplication of three factors:
function minimization, Branch-and-Bound search, and
solving Equations~\eq{eq:chain:even:shared} and \eq{eq:chain:odd:shared}
for the case of two agents or Equation~\eq{eq:zeta:main:nagents} for
the general case.
For two agents, the only exponential component is the Branch-and-Bound search.
We found, however, that in practice the branching factor, which is roughly
the number of roots of the equations above,
is rather small, while the depth of the search tree
can be controlled by iterative-deepening strategies.
For an arbitrary number of agents, function minimization may also
be exponential.  In practice, however, it depends on the behavior 
of the minimized 
function and the minimization algorithm.

Since the optimal schedule is static and can be applied
to a large number of problem instances, 
its computation
is beneficial even when associated with high cost.
Moreover, in some applications (such as robotic search) the
computational cost can be outweighed by the gain obtained
from a single invocation.

The previous work most related to our research is the restart framework
\cite{Luby:1993:OSL}.  The most important difference between our algorithm and 
the restart policy is the ability to handle the cases where the number
of runs is limited, or where different algorithms
are involved. When only one algorithm is available and the number of
runs is infinite, the restart strategy is optimal. However, as we have shown in
Section~\ref{sec:LS:restarts}, some problems may benefit from the combination
of these two approaches.

Our algorithm 
 assumes the availability of the performance profiles
of the processes.  Such performance profiles can be derived 
analytically using theoretical models of the processes or empirically from 
previous experience with solving similar problems.  
Online learning of performance profiles, which could expand
the applicability of the proposed framework, is a subject of ongoing research.


The framework presented here can be used for a wide range of 
applications.  In the introduction we presented three examples.
The first example describes two alternative learning algorithms
working in parallel.  The behavior of such algorithms is
usually exponential, and the analysis for such setup
is given in  Section \ref{sec:exponential}.  
The second example is a CSP problem
with two alternative initial configurations, which 
is analogous to the Latin Square example of Sections
\ref{sec:LS} and \ref{sec:experiments}.  The last example
includes crawling processes with a limited shared
bandwidth. Unlike the first two examples, this
setup falls under the framework of intensity control
described in Section \ref{sec:intensity}.

 


Similar schemes may be applied for more elaborate setups:
\begin{itemize}
\item Scheduling a system of $n$ anytime algorithms, where the overall cost
of the system is defined as the maximal cost of its components 
(unlike the analysis in Section \ref{sec:suspend:resume}, this function
is not differentiable);
\item Scheduling with non-zero process switch costs;
\item Providing dynamic scheduling algorithms able to handle changes in
the environment;
\item Building effective algorithms for the case of several resources
of different types, e.g., multiprocessor systems.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\appendix

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Formal Proofs}
\subsection{Proof of Lemma~\ref{lemma:u:nagents}}
\label{proof:lemma:u:nagents}
The claim of the lemma is as follows:

\begin{em}
For a system of $n$ processes, the expression
for the expected cost~\eq{eq:main:sigma:shared} can be rewritten
as
\begin{equation}\label{eq:u:main:nagents:proof}
E_u(\zeta_1, \ldots, \zeta_n, \ldots) =
\sum_{k=0}^\infty
\sum_{i=1}^{n} \prod_{j=i+1}^{i+n-1} (1-F_{\remj}(\zeta^j_{k-1}))
\int_{\zeta^i_{k-1}}^{\zeta^i_k}
(1-F_i(x))\dx.
\end{equation}
\end{em}

\begin{proof}
Splitting the whole integration range $[0,\infty)$
to the intervals $[t^{i-1}_k,t^i_k]$ yields the following expression:
\begin{equation}
E_u(\sigma_1, \ldots, \sigma_n) =
\int_0^\infty\prod_{j=1}^n(1-F_j(\sj))\dt =
\sum_{k=0}^{\infty}\sum_{i=1}^{n}
\int_{t^{i-1}_k}^{t^i_k}\prod_{j=1}^n(1-F_j(\sj))\dt.
\label{eq:lemma:u:nagents:1:proof}
\end{equation}
By~\eq{eq:sigmazeta:n}, we can rewrite the inner integral as
\begin{equation}
\begin{split}
&\int_{t^{i-1}_k}^{t^i_k} \prod_{j=1}^n(1-F_j(\sj)) =\\
&\int_{t^{i-1}_k}^{t^i_k}\left[\prod_{j=1}^{i-1}(1-F_j(\zeta^j_k)) \cdot
(1-F_i(t - t^{i-1}_k + \zeta^i_{k-1})) \cdot
\prod_{j=i+1}^{n}(1-F_j(\zeta^j_{k-1}))\right]\dt =\\
& \prod_{j=i+1-n}^{i-1}(1-F_{\remj}(\zeta^j_k))
\int_{t^{i-1}_k}^{t^i_k} (1-F_i(t - t^{i-1}_k + \zeta^i_{k-1}))\dt.
\end{split}
\label{eq:lemma:u:nagents:2:proof}
\end{equation}
Substituting $x$ for $t - t^{i-1}_k + \zeta^i_{k-1}$ and
using~\eq{eq:zetabyt:n}, we obtain
\begin{equation}
\begin{split}
& \prod_{j=i+1-n}^{i-1}(1-F_{\remj}(\zeta^j_k))
\int_{t^{i-1}_k}^{t^i_k} (1-F_i(t - t^{i-1}_k + \zeta^i_{k-1}))\dt =\\
&\prod_{j=i+1}^{i+n-1}(1-F_{\remj}(\zeta^j_{k-1}))
\int_{\zeta^i_{k-1}}^{t^i_k - t^{i-1}_k + \zeta^i_{k-1}}
(1-F_i(x))\dx =\\
&\prod_{j=i+1}^{i+n-1}(1-F_{\remj}(\zeta^j_{k-1}))
\int_{\zeta^i_{k-1}}^{\zeta^i_k}(1-F_i(x))\dx.
\end{split}
\label{eq:lemma:u:nagents:3:proof}
\end{equation}
Combining~\eq{eq:lemma:u:nagents:1:proof},~\eq{eq:lemma:u:nagents:2:proof}
and~\eq{eq:lemma:u:nagents:3:proof} gives us~\eq{eq:u:main:nagents:proof}.
\end{proof}

\subsection{Proof of the Chain Theorem for $n$ Processes}
\label{proof:th:chain}
The chain theorem claim is as follows:

\begin{em}
The value for $\zeta_{m+1}^{l-1}$ may either be $\zeta_m^{l-1}$, or can be
computed given the previous $2n-2$ values of $\zeta$ using  
the formula
\begin{equation}
\frac{f_l(\zeta^l_m)}{1-F_l(\zeta^l_m)} =
\frac{\displaystyle
\prod_{j=l+1}^{l+n-1}(1-F_{\remj}(\zeta^j_{m-1})) -
\prod_{j=l+1}^{l+n-1}(1-F_{\remj}(\zeta^j_m))
}
{\displaystyle
\sum_{i=l-n+1}^{l-1}\prod_{\substack{j=i+1\\ \remj\neq l}}^{i+n-1}(1-F_{\remj}
(\zeta^j_m))
\int_{\zeta^i_m}^{\zeta^i_{m+1}}(1-F_{\remi}(x))\dx
}
\label{eq:zeta:main:nagents:proof}
\end{equation}
\end{em}
\begin{proof}
By Lemma~\ref{lemma:u:nagents}, the expression we want to minimize is
described by the equation
\begin{equation}
E_u(\zeta_1, \ldots, \zeta_n, \ldots) = \sum_{k=0}^\infty
\sum_{i=1}^{n} \prod_{j=i+1}^{i+n-1} (1-F_{\remj}(\zeta^j_{k-1}))
\int_{\zeta^i_{k-1}}^{\zeta^i_k}(1-F_i(x))\dx.
\label{eq:u:main:nagents:proof:copy}
\end{equation}
The expression above reaches its optimal values either when
\begin{equation}
\frac{dE_u}{d\zeta_j} = 0 \; \mbox {for} \; j = 1,\ldots, n,\ldots,
\end{equation}
or on the border described by~\eq{eq:zeta:series:n}.

Reaching the optimal values on the border corresponds to the first alternative
described in the theorem. Let us now consider a case when the derivative of
$E_u$ by $\zeta_j$ is $0$.

Each variable $\zeta_j$ may be presented as $\zeta_{mn+l} = \zeta^l_m$,
where $0 \leq l \leq n-1$.
Let us see which summation terms of~\eq{eq:u:main:nagents:proof:copy}
$\zeta^l_m$ is participating in.

\begin{enumerate}
\item $\zeta^l_m$ may be a lower bound of the integral
from~\eq{eq:u:main:nagents:proof:copy}. This happens when $k = m+1$ and $i = l$.
The corresponding term is
\[
S_0 = \prod_{j=l+1}^{l+n-1} (1-F_{\remj}(\zeta^j_m))
\int_{\zeta^l_m}^{\zeta^l_{m+1}}(1-F_l(x))\dx,
\]
and
\[
\frac{dS_0}{d\zeta^l_m} =
-(1-F_l(\zeta^l_m))\cdot \prod_{j=l+1}^{l+n-1} (1-F_{\remj}(\zeta^j_m)).
\]

\item $\zeta^l_m$ may be an upper bound of the same integral,
which happens when $k=m$ and $i=l$.
The corresponding term is
\[
S_l = \prod_{j=l+1}^{l+n-1} (1-F_{\remj}(\zeta^j_{m-1}))
\int_{\zeta^l_{m-1}}^{\zeta^l_m}(1-F_l(x))\dx,
\]
and
\[
\frac{dS_l}{d\zeta^l_m} =
(1-F_l(\zeta^l_m))\cdot
\prod_{j=l+1}^{l+n-1} (1-F_{\remj}(\zeta^j_{m-1})).
\]

\item Finally, $\zeta^l_m$ may participate in the product
\[
\prod_{j=i+1}^{i+n-1} (1-F_{\remj}(\zeta^j_{k-1})).
\]
For $i = 1\ldots l-1$, this may happen when $k=m+1$ and $j=l$,
and the corresponding term is
\[
S_i = \prod_{j=i+1}^{i+n-1} (1-F_{\remj}(\zeta^j_m))
\int_{\zeta^i_m}^{\zeta^i_{m+1}}(1-F_i(x))\dx,
\]
with the derivative
\[
\frac{dS_i}{d\zeta^l_m} =
-f_l(\zeta^l_m) \prod_{j=i+1,\remj\neq l}^{i+n-1} (1-F_{\remj}(\zeta^j_m))
\int_{\zeta^i_m}^{\zeta^i_{m+1}}(1-F_i(x))\dx.
\]
For $i = l+1\ldots n$, $k=m$ and $j=l+n$. The corresponding term is
\[
S_i = \prod_{j=i+1}^{i+n-1} (1-F_{\remj}(\zeta^j_{m-1}))
\int_{\zeta^i_{m-1}}^{\zeta^i_m}(1-F_i(x))\dx,
\]
with the derivative
\[
\frac{dS_i}{d\zeta^l_m} =
-f_l(\zeta^l_m)
\prod_{j=i+1,\remj\neq l}^{i+n-1} (1-F_{\remj}(\zeta^j_{m-1}))
\int_{\zeta^i_{m-1}}^{\zeta^i_m}(1-F_i(x))\dx.
\]
\end{enumerate}
Since for $i = l$, $\zeta^l_m$ appears only in the integral,
there is no other possibility for $\zeta^l_m$ to appear in the expression,
and therefore
\[
\frac{dE_u}{d\zeta^l_m} = \sum_{i=0}^{n} \frac{dS_i}{d\zeta^l_m}.
\]
The right-hand side of the sum above can be written as follows:
\begin{eqnarray}
&&\sum_{i=0}^{n} \frac{dS_i}{d\zeta^l_m}=\nonumber\\
&&-(1-F_l(\zeta^l_m))\prod_{j=l+1}^{l+n-1} (1-F_{\remj}(\zeta^j_m))
+
(1-F_l(\zeta^l_m))
\prod_{j=l+1}^{l+n-1} (1-F_{\remj}(\zeta^j_{m-1})) -\nonumber\\
&&\sum_{i=1}^{l-1} f_l(\zeta^l_m)
\prod_{j=i+1,\remj\neq l}^{i+n-1} (1-F_{\remj}(\zeta^j_m))
\int_{\zeta^i_m}^{\zeta^i_{m+1}}(1-F_i(x))\dx -\nonumber\\
&&\sum_{i=l+1}^n f_l(\zeta^l_m)
\prod_{j=i+1,\remj\neq l}^{i+n-1} (1-F_{\remj}(\zeta^j_{m-1}))
\int_{\zeta^i_{m-1}}^{\zeta^i_m}(1-F_i(x))\dx.
\label{proof:th:chain:1}
\end{eqnarray}
However,
\begin{eqnarray}
&&\sum_{i=l+1}^n
\prod_{j=i+1,\remj\neq l}^{i+n-1} (1-F_{\remj}(\zeta^j_{m-1}))
\int_{\zeta^i_{m-1}}^{\zeta^i_m}(1-F_i(x))\dx=\nonumber\\
&&\sum_{i=l-n+1}^0
\prod_{j=i+1,\remj\neq l}^{i+n-1} (1-F_{\remj}(\zeta^j_m))
\int_{\zeta^i_m}^{\zeta^i_{m+1}}(1-F_i(x))\dx.
\label{proof:th:chain:2}
\end{eqnarray}
Substituting~\eq{proof:th:chain:2} into~\eq{proof:th:chain:1},
we obtain
\begin{eqnarray}
&&\sum_{i=0}^{n} \frac{dS_i}{d\zeta^l_m}=\nonumber\\
&&
(1-F_l(\zeta^l_m))
\left(\prod_{j=l+1}^{l+n-1} (1-F_{\remj}(\zeta^j_{m-1})) -
      \prod_{j=l+1}^{l+n-1} (1-F_{\remj}(\zeta^j_m))\right) -
\nonumber\\
&&f_l(\zeta^l_m)
\sum_{i=l-n+1}^{l-1}
\prod_{j=i+1,\remj\neq l}^{i+n-1} (1-F_{\remj}(\zeta^j_m))
\int_{\zeta^i_m}^{\zeta^i_{m+1}}(1-F_i(x))\dx.
\label{proof:th:chain:3}
\end{eqnarray}
If $1-F_l(\zeta^l_m)$ were $0$, that would mean that the goal has
been reached with the probability of $1$, and further scheduling would be
redundant. Otherwise, expression in~\eq{proof:th:chain:3} is $0$
when
\[
\frac{f_l(\zeta^l_m)}{1-F_l(\zeta^l_m)} =
\frac{
{\displaystyle
\prod_{j=l+1}^{l+n-1}(1-F_{\remj}(\zeta^j_{m-1})) -
\prod_{j=l+1}^{l+n-1}(1-F_{\remj}(\zeta^j_m))
}}
{
{\displaystyle
\sum_{i=l-n+1}^{l-1}\prod_{j=i+1,\remj\neq l}^{i+n-1}(1-F_{\remj}
(\zeta^j_m))
\int_{\zeta^i_m}^{\zeta^i_{m+1}}(1-F_{\remi}(x))\dx
}},
\]
which is equivalent to~\eq{eq:zeta:main:nagents:proof}.

Equation~\eq{eq:zeta:main:nagents:proof} includes $2n-1$ variables
($\zeta^{l+1}_{m-1} = \zeta_{n(m-1)+l+1}$ to
$\zeta^{l-1}_{m+1} = \zeta_{n(m+1)+l-1}$), providing an implicit 
dependency of $\zeta^{l-1}_{m+1}$ on the remaining $2n-2$ variables.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Proof of Lemma~\ref{lemma:euler}}
\label{proof:lemma:euler}
The claim of the lemma is as follows:

\begin{em}
The Euler-Lagrange conditions for the minimization problem~\eq{eq:main:sigma}
yield two strong invariants:
\begin{enumerate}
\item For processes $k_1$ and $k_2$ for which $\sigma_{k_1}$ and $\sigma_{k_2}$
are not on the border described by~\eq{eq:constraint:shared}, the distribution
and density functions satisfy
\begin{equation}
\frac{f_{k_1}(\sigma_{k_1})}{1-F_{k_1}(\sigma_{k_1})} =
\frac{f_{k_2}(\sigma_{k_2})}{1-F_{k_2}(\sigma_{k_2})}.
\label{eq:invariant:h:proof}
\end{equation}
\item If the schedules of \emph{all} the processes are not on the
border described by~\eq{eq:constraint:shared}, then either
$c = 1$ or $f_k(\sigma_k) = 0$ for each $k$.
\end{enumerate}
\end{em}

\begin{proof}
Let $g(t, \sigma_1, \ldots, \sigma_n, \sigma'_1, \ldots, \sigma'_n)$
be the function under the integral sign of~\eq{eq:main:sigma}:
\begin{equation}
g(t, \sigma_1, \ldots, \sigma_n, \sigma'_1, \ldots, \sigma'_n) =
\left((1-c) + c\sum_{i=1}^n\sip\right)
\prod_{j=1}^n(1-F_j(\sj)).
\label{eq:functional:g:proof}
\end{equation}
A necessary condition of Euler-Lagrange
claims that a set of functions $\sigma_1, \ldots, \sigma_n$ provides a weak
(local) minimum to the functional
\begin{equation*}
E_u(\sigma_1, \ldots, \sigma_n) = \int_0^\infty
g(t, \sigma_1, \ldots, \sigma_n, \sigma'_1, \ldots, \sigma'_n)\dt
\end{equation*}
only if these functions satisfy a system of equations of the form
\begin{equation}
g'_{\sigma_k} - \frac{d}{dt}g'_{\sigma_k'} = 0.
\label{eq:euler:proof}
\end{equation}
In our case,
\begin{equation}
g'_{\sigma_k} = -\left((1-c) + c\sum_{i=1}^n\sip\right)
f_k(\sigma_k)\prod_{j\neq k}(1-F_j(\sj)),
\label{eq:g:sigma:proof}
\end{equation}
and
\begin{equation}
\frac{d}{dt}g'_{\sigma_k'} = c\frac{d}{dt}\prod_{j=1}^n(1-F_j(\sj)) =
-c\sum_{l=1}^n \sigma_l' f_l(\sigma_l)\prod_{j\neq l}(1-F_j(\sigma_j)).
\label{eq:g:sigmap:proof}
\end{equation}
Substituting the last expression into~\eq{eq:euler:proof}, we obtain
\begin{equation*}
g'_{\sigma_1} = g'_{\sigma_2} = \ldots = g'_{\sigma_n} =
-c\sum_{l=1}^n \sigma_l' f_l(\sigma_l)\prod_{j\neq l}(1-F_j(\sigma_j)),
\end{equation*}
and by~\eq{eq:g:sigma:proof} for every $k_1$ and $k_2$
\begin{equation*}
f_{k_1}(\sigma_{k_1})\prod_{j\neq k_1}(1-F_j(\sj)) =
f_{k_2}(\sigma_{k_2})\prod_{j\neq k_2}(1-F_j(\sj)).
\end{equation*}
We can ignore the case where one of the terms $1-F_j(\sigma_j)$
is $0$. Indeed, this is possible only if the goal is reached by process $j$
with probability of $1$, and in this case no optimization is needed. Therefore,
we obtain
\begin{equation}
f_{k_1}(\sigma_{k_1})(1-F_{k_2}(\sigma_{k_2})) =
f_{k_2}(\sigma_{k_2})(1-F_{k_1}(\sigma_{k_1})),
\label{eq:invariant:0:proof}
\end{equation}
which is equivalent to~\eq{eq:invariant:h:proof}.

Let us show now the correctness of the second invariant.
By~\eq{eq:g:sigmap:proof} and~\eq{eq:invariant:h:proof}, we obtain
\begin{equation*}
\begin{split}
\frac{d}{dt}g'_{\sigma_k'} = &
-c\sum_{l=1}^n \sigma_l' f_l(\sigma_l)\prod_{j\neq l}(1-F_j(\sigma_j)) =\\
& -c\sum_{l=1}^n \sigma_l' \frac{f_l(\sigma_l)}{1-F_l(\sigma_l)}
\prod_{j=1}^n(1-F_j(\sigma_j)) =\\
& -c\sum_{l=1}^n \sigma_l' \frac{f_k(\sigma_k)}{1-F_k(\sigma_k)}
\prod_{j=1}^n(1-F_j(\sigma_j)) =\\
& -c\left(\sum_{i=1}^n \sigma_i'\right)
f_k(\sigma_k)\prod_{j\neq k}(1-F_j(\sigma_j)).
\end{split}
\end{equation*}
By~\eq{eq:euler} we get
\begin{equation*}
\begin{split}
g'_{\sigma_k} - \frac{d}{dt}g'_{\sigma_k'} = & 
-\left((1-c) + c\sum_{i=1}^n\sip\right)
f_k(\sigma_k)\prod_{j\neq k}(1-F_j(\sj))\\
& + c\left(\sum_{i=1}^n \sip\right)
f_k(\sigma_k)\prod_{j\neq k}(1-F_j(\sigma_j)) = \\
& -(1-c) f_k(\sigma_k)\prod_{j\neq k}(1-F_j(\sj)) = 0.
\end{split}
\end{equation*}
Since we ignore the case when $(1-F_j(\sj)) = 0$, the second
invariant is correct.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Proof of Lemma~\ref{lemma:max:resources}}
\label{proof:lemma:max:resources}
The claim of the lemma is as follows:

\begin{em}
If an optimal solution exists, then there exists an optimal solution
$\sigma_1, \ldots, \sigma_n$, such that at each time $t$ all the resources
are consumed, i.e.,
\[
\forall t \; \sum_{i=1}^n \sigma'_i(t) = 1.
\]
In the case where time cost is not zero ($c \neq 1$), the equality above
is a necessary condition for solution optimality.
\end{em}

\begin{proof}
We know that $\{\sigma_i\}$ provide a minimum for the
expression~\eq{eq:main:sigma}
\[
\int_0^\infty\left((1-c) + c\sum_{i=1}^n\sip\right)
\prod_{j=1}^n(1-F_j(\sj))\dt.
\]
Let us assume that in some time interval $[t_0, t_1]$, $\{\sigma_i\}$ do
not satisfy the lemma's constraints.
However, it is possible to use the same amount of resources more effectively.
Let us consider a linear time warp $\nu(t) = \alpha t + \beta$ on the
time interval $[t_0, t_1]$, satisfying $\nu(t_0) = t_0$. From the last
condition, it follows that $\beta = t_0(1-\alpha)$. Let $t'_1$ be a point where
$\nu(t)$ achieves $t_1$, i.e., $t'_1 = t_0 + (t_1 - t_0) / \alpha$.
Let us consider a set of new objective schedule functions
$\widetilde{\sigma}_i(t)$ of the form
\[
\widetilde{\sigma}_i(t) =
\left\{
\begin{array}{ll}
\sigma_i(t), & t \leq t_0,\\
\sigma_i(\alpha t + \beta), & t_0 \leq t \leq t'_1,\\
\sigma_i(t + t_1 - t'_1), & t > t'_1.
\end{array}
\right.
\]
Thus, $\widetilde{\sigma}_i(t)$ behaves as $\sigma_i(t)$ before $t_0$,
as $\sigma_i(t)$ with a time shift after $t'_1$, and as a linearly speeded
up version of $\sigma_i(t)$ in the interval $[t_0, t'_1]$.
Since $\nu(t_0) = t_0$ and $\nu(t'_1) = t_1$, $\widetilde{\sigma}_i(t)$
is continuous at the points $t_0$ and $t'_1$.

$\widetilde{\sigma}_i'(t)$ is equal to $\alpha \sigma_i'(t)$ within
the interval $[t_0, t_1]$, and to $\sigma_i'(t)$ outside this interval.
By the contradiction assumption, $\sigma_i$ do not meet the lemma constraints
in $[t_0, t_1]$, and thus we can take
\[
\alpha = \frac{1}{\max_{t\in[t_0, t_1]} \sum_{i=1}^n \sigma'_i(t)}  > 1,
\]
leading to valid functions $\widetilde{\sigma}_i'(t)$.
Using $\widetilde{\sigma}_i(t)$ in~\eq{eq:main:sigma}, we obtain
\begin{eqnarray*}
E_u(\widetilde{\sigma}_1, \ldots, \widetilde{\sigma}_n) & = &
\int_0^\infty\left((1-c) + c\sum_{i=1}^n\widetilde{\sigma}_i'(t)\right)
\prod_{j=1}^n(1-F_j(\widetilde{\sigma}_j(t)))\dt =\\
&& \int_0^{t_0}\left((1-c) + c\sum_{i=1}^n\sigma'_i(t)\right)
\prod_{j=1}^n(1-F_j(\sigma_j(t)))\dt +\\
&&\int_{t_0}^{t'_1}\left((1-c) + c\alpha\sum_{i=1}^n\sigma'_i(\alpha t+\beta)\right)
\prod_{j=1}^n(1-F_j(\sigma_j(\alpha t+\beta)))\dt +\\
&&\int_{t'_1}^{\infty}\left((1-c) + c\sum_{i=1}^n\sigma'_i(t + t_1 - t'_1)\right)
\prod_{j=1}^n(1-F_j(\sigma_j(t + t_1 - t'_1)))\dt.
\end{eqnarray*}
By substituting $x = \alpha t + \beta$ in the second term of the last sum,
and $x = t + t_1 - t'_1$ in the third term, we obtain
\begin{eqnarray*}
E_u(\widetilde{\sigma}_1, \ldots, \widetilde{\sigma}_n) & = &
\int_0^{t_0}\left((1-c) + c\sum_{i=1}^n\sigma'_i(t)\right)
\prod_{j=1}^n(1-F_j(\sigma_j(t)))\dt +\\
&&\int_{t_0}^{t_1}\left(\frac{1-c}{\alpha} + c\sum_{i=1}^n\sigma'_i(x)\right)
\prod_{j=1}^n(1-F_j(\sigma_j(x)))\dx +\\
&&\int_{t_1}^{\infty}\left((1-c) + c\sum_{i=1}^n\sigma'_i(x)\right)
\prod_{j=1}^n(1-F_j(\sigma_j(x)))\dx =\\
&& E_u(\sigma_1, \ldots, \sigma_n) -
\int_{t_0}^{t_1}(1-c)\left(1-\frac{1}{\alpha}\right)\prod_{j=1}^n(1-F_j(\sigma_j))\dt.
\end{eqnarray*}
Since $\alpha > 1$, the last term is non-negative, and therefore
\begin{eqnarray*}
E_u(\widetilde{\sigma}_1, \ldots, \widetilde{\sigma}_n) \leq
E_u(\sigma_1, \ldots, \sigma_n),
\end{eqnarray*}
meaning that the set $\{\widetilde{\sigma}_i\}$ provides a solution
of at least the same quality as $\{\sigma_i\}$. If $c \neq 1$, this
contradicts to the optimality of the original schedule, and if $c = 1$,
the new schedule will also be optimal.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Proof of Theorem~\ref{th:no-intensity:shared}}
\label{proof:th:no-intensity:shared}
The claim of the theorem is as follows:

\begin{em}
Let the set of functions $\{\si\}$ be a solution of
minimization problem~\eq{eq:main:sigma:shared} under
constraints~\eq{eq:constraint:shared}. Let $t_0$ be a point where
the hazard functions of all the processes $h_i(\sigma_i(t))$ are continuous,
and let $A_k$ be the process active at $t_0$ ($\sigma_k'(t_0) > 0$), such that
for any other process $A_i$ 
\begin{equation}
h_i(\sigma_i(t_0)) < h_k(\sigma_k(t_0)).
\end{equation}
Then at $t_0$ process $k$ consumes all the resources, i.e. $\sigma_k'(t_0) = 1$.
\end{em}

\begin{proof}
First we want to prove the theorem for the case of two processes,
and then to generalize the proof to the case of $n$ processes.
Assume that $\sigma_1(t)$ and $\sigma_2(t)$ provide the optimal solution,
and at some point $t_0$ $\sigma'_1(t_0) > 0$ and 
\begin{equation}
\frac{f_1(\sigma_1(t_0))}{1-F_1(\sigma_1(t_0))} >
\frac{f_2(\sigma_2(t_0))}{1-F_2(\sigma_2(t_0))}.
\label{eq:shared:ineq}
\end{equation}
From the continuity of the functions $h_i(t)$
in the point $t_0$, it follows that there exists some neighborhood $U(t_0)$ of
$t_0$, such that for each two points $t', t''$ in this neighborhood
$h_1(t') > h_2(t'')$, i.e.,
\begin{equation}
\min_{t'\in U(t_0)} \frac{f_1(\sigma_1(t'))}{1-F_1(\sigma_1(t'))} >
\max_{t''\in U(t_0)} \frac{f_2(\sigma_2(t''))}{1-F_2(\sigma_2(t''))}.
\label{eq:shared:minmax}
\end{equation}
Let us consider some interval $[t_0, t_1] \subset U(t_0)$.
In order to make the proof more readable, we introduce
the following notation (for this proof only):
\begin{itemize}
\item We denote $\sigma_1(t)$ by $\sigma(t)$. By
Lemma~\ref{lemma:max:resources}, $\sigma_2(t) = t - \sigma(t)$.
\item We denote $\sigma(t_0)$ by $\sigma^0$ and $\sigma(t_1)$ by $\sigma^1$.
\end{itemize}
In the interval $[t_0, t_1]$ the first process obtains $\st^1 - \st^0$ resources,
and the second process obtains $(t_1 - t_0) - (\st^1 - \st^0)$ resources.
Let us consider a special resource distribution $\widetilde{\sigma}$, which
first gives all the resources to the first process, and then to the second process,
keeping the same quantity of resources as $\sigma$:
\[
\wst(t) = \left\{
\begin{array}{ll}
\st(t), & t \leq t_0,\\
t - t_0 + \st^0, & t_0 \leq t \leq t_0 + \st^1 - \st^0,\\
\st^1, & t_0 + \st^1 - \st^0 \leq t \leq t_1\\
\st(t), & t \geq t_1.
\end{array}
\right.
\]
It is easy to see that $\st(t)$ is continuous at the points $t_0$, $t_1$,
and $t_0 + \st^1 - \st^0$.
We want to show that,  unless the first 
process consumes all the resources at the beginning,
the schedule produced by $\wst$
outperforms the schedule produced by $\st$.

Let $t^* = t_0 + \st^1 - \st^0$, which corresponds to the time when
the first process would have consumed all its resources had it been working
with the maximal intensity.
First, we want to show that in the interval $[t_0, t^*]$
\begin{equation}
(1-F_1(\st(t)))(1-F_2(t-\st(t))) \geq (1-F_1(t-t_0+\st^0))(1-F_2(t_0-\st^0)).
\label{eq:shared:part1}
\end{equation}
Let
\begin{equation}
\nu(t) = (t - t_0 + \st^0) - \sigma(t).
\label{eq:nu:1}
\end{equation}
The inequality~\eq{eq:shared:part1} becomes
\begin{equation}
(1-F_1(t-t_0+\st^0-\nu(t)))(1-F_2(t_0-\st^0+\nu(t))) \geq
(1-F_1(t-t_0+\st^0))(1-F_2(t_0-\st^0)).
\label{eq:shared:part1:1}
\end{equation}
Let us find a value of $x = \nu(t)$ that provides the minimum
to the left-hand side of~\eq{eq:shared:part1:1} for the fixed $t$.
Let us denote
\[
G(x) = (1-F_1(t-t_0+\st^0-x))(1-F_2(t_0-\st^0+x)).
\]
Then,
\[
G'(x) = f_1(t-t_0+\st^0-x))(1-F_2(t_0-\st^0+x)) -
f_2(t_0-\st^0+x)(1-F_1(t-t_0+\st^0-x)).
\]
Since a valid $\sigma(t)$ in the interval $[t_0, t_1]$ 
obtains values between $\st^0$ and $\st^1$, by~\eq{eq:nu:1} we have
\begin{eqnarray*}
&&t - t_0 + \st^0 - x \in [\st^0, \st^1],\\
&&t_0 - \st^0 + x \in [t_0-\st^0, t_1-\st^1].
\end{eqnarray*}
Therefore, there exist $t', t'' \in [t_0, t_1]$, such that
$\sigma_1(t') = \sigma(t') = t - t_0 + \st^0 - x$ and 
$\sigma_2(t'') = t'' - \sigma(t'') = t_0 - \st^0 + x$.
By~\eq{eq:shared:minmax} we obtain $G'(x) > 0$, meaning that
$G(x)$ monotonically increases. Besides, by~\eq{eq:nu:1} 
we have $x = \nu(t) \geq 0$ (since $\sigma'(t) \leq 1$),
and therefore $G(x)$ obtains its minimal value when $x = 0$.
Therefore, if we denote by $Ran(t)$ the set of valid values for $\nu(t)$,
\begin{equation*}
\begin{split}
&(1-F_1(\st))(1-F_2(t - \st)) =
(1-F_1(t-t_0+\st^0-\nu(t)))(1-F_2(t_0-\st^0+\nu(t))) \geq\\
& \min_{x\in Ran(t)} (1-F_1(t-t_0+\st^0-x))(1-F_2(t_0-\st^0+x)) =\\
&(1-F_1(t-t_0+\st^0))(1-F_2(t_0-\st^0)),
\end{split}
\end{equation*}
and the strict equality occurs if and only if $\sigma(t) = t - t_0 + \st^0$.
Thus,
\begin{equation*}
(1-F_1(\sigma))(1-F_2(t-\sigma)) \geq (1-F_1(\wst))(1-F_2(t-\wst))
\end{equation*}
for $t \in [t_0, t^*]$.

Let us show now the correctness of the same statement in the interval
$[t^*, t_1]$, which is equivalent to the inequality
\begin{equation}
(1-F_1(\st(t)))(1-F_2(t-\st(t))) \geq (1-F_1(\st^1))(1-F_2(t-\st^1)).
\label{eq:shared:part2}
\end{equation}
The proof is similar. Let
\begin{equation}
\nu(t) = \st^1 - \sigma(t).
\label{eq:nu:2}
\end{equation}
The inequality~\eq{eq:shared:part2} becomes
\begin{equation}
(1-F_1(\st^1-\nu(t)))(1-F_2(t-\st^1+\nu(t))) \geq
(1-F_1(\st^1))(1-F_2(t-\st^1)).
\label{eq:shared:part2:1}
\end{equation}
As before, we find a value of $x = \nu(t)$ that provides the minimum
to the left-hand side of~\eq{eq:shared:part2:1} 
\[
G(x) = (1-F_1(\st^1-x))(1-F_2(t-\st^1+x)).
\]
The derivative of $G(x)$ is
\[
G'(x) = f_1(\st^1-x))(1-F_2(t-\st^1+x)) - f_2(t-\st^1+x)(1-F_1(\st^1-x)),
\]
and since a valid $\sigma(t)$ in the interval $[t_0, t_1]$ 
obtains values between $\st^0$ and $\st^1$, by~\eq{eq:nu:2} we have
\begin{eqnarray*}
&&\st^1-x \in [\st^0, \st^1],\\
&&t-\st^1+x\in [t_0-\st^0, t_1-\st^1].
\end{eqnarray*}
Therefore, there exist $t', t'' \in [t_0, t_1]$, such that
$\sigma_1(t') = \sigma(t') = \st^1-x$ and 
$\sigma_2(t'') = t'' - \sigma(t'') = t-\st^1+x$.
By~\eq{eq:shared:minmax}, $G'(x) > 0$, and therefore $G(x)$ monotonically
increases. Since $x = \sigma^1 - \sigma(t) \geq 0$, $G(x) \geq G(0)$.
Thus, for $t \in [t^*,t_1]$,
\begin{equation*}
\begin{split}
&(1-F_1(\st))(1-F_2(t - \st)) =
(1-F_1(\st^1-\nu(t)))(1-F_2(t-\st^1+\nu(t))) \geq\\
&\min_{x\in Ran(t)} (1-F_1(\st^1-x))(1-F_2(t-\st^1+x)) =
(1-F_1(\st^1))(1-F_2(t-\st^1)),
\end{split}
\end{equation*}
and the strict equality occurs if and only if $\sigma(t) = \st^1$.

Combining this result with the previous one, we obtain that
\begin{equation*}
(1-F_1(\sigma))(1-F_2(t-\sigma)) \geq (1-F_1(\wst))(1-F_2(t-\wst))
\end{equation*}
holds for every $t\in[t_0, t_1]$. 
Since $\wst(t)$ behaves as $\sigma(t)$ outside this interval,
$E_u(\sigma) \geq E_u(\wst)$. Besides, since the equality 
is obtained if and only if $\sigma \equiv \wst$, and since $E_u(\sigma)$ is 
optimal,
we obtain that $\sigma \equiv \wst$, and therefore the first process will take
all the resources in some interval $[t_0, t_1]$.

The proof for $n$ processes is exactly the same. Let $\{\sigma_i\}$ provide
the optimal solution, and at the point $t_0$ there is process $k$, such that
for each $j\neq k$
\[
h_k(\sigma_k(t_0)) > h_j(\sigma_j(t_0)).
\]
From the continuity of the functions $h_i(\sigma_i(t))$
in the point $t_0$, it follows that there exists some neighborhood $U(t_0)$ of
$t_0$, such that
\begin{equation}
\min_{t'\in U(t_0)} h_k(\sigma_k(t')) > 
\max_{i\neq k} \max_{t''\in U(t_0)} h_i(\sigma_i(t'')).
\label{eq:shared:minmax:2}
\end{equation}
Let us take any process $l\neq k$, and let
\[
y(t) = \sigma_k(t) + \sigma_l(t).
\]
Now we can repeat the above proof while substituting $y(t)$ instead of $t$ 
under the function sign:
\[
\wst_k(t) = \left\{
\begin{array}{ll}
\st_k(t), & y(t) \leq y(t_0),\\
y(t) - y(t_0) + \st_k(t_0), & y(t_0) \leq y(t) \leq y(t_0) + 
                              \st_k(t_1) - \st_k(t_0),\\
\st_k(t_1), & y(t_0) + \st_k(t_1) - \st_k(t_0) \leq y(t) \leq y(t_1),\\
\st_k(t), & y(t) \geq y(t_1).
\end{array}
\right.
\]
The substitution above produces a valid schedule due to the monotonicity of 
$y(t)$. The rest of the proof remains unchanged.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Proof of Theorem~\ref{th:h:control:increasing}}
\label{proof:th:h:control:increasing}
The claim of the theorem is as follows:

\begin{em}
An active process will remain active and consume all resources
as long as its hazard function is monotonically increasing.
\end{em}

\begin{proof}
The proof is by contradiction. Let $\{\sigma_j\}$ form an optimal
schedule. Assume that at some point $t_1$ 
process $A_k$ is suspended, while its hazard function $h_k(\sigma_k(t_1))$
is monotonically increasing at $t_1$.

Let us assume first that at some point $t_2$ process $A_k$ becomes active
again. Since we do not consider the case of making process active at a single
point, there exists some $\Delta > 0$, such that
$A_k$ is active in the intervals $[t_1 - \Delta, t_1]$ and
$[t_2, t_2+\Delta]$.
$A_k$ has been stopped at a point of monotonicity of the
hazard function, and therefore, by Theorem~\ref{th:no-intensity:shared},
in these intervals $A_k$ is the only active process.
We consider two alternative scenarios. In the first one,
we allow $A_k$ to be active for additional $\Delta$ time starting at $t_1$
(i.e., shifting its idle period by $\Delta$), while in the second we suspend
$A_k$ by $\Delta$ earlier.

For the first scenario, the scheduling functions have the following form:
\begin{align}
&\sigma^a_{k}(t) = \left\{
\begin{array}{ll}
\sigma_k(t), & t \leq t_1,\\
\sigma_k(t_1) + (t-t_1), & t_1 \leq t \leq t_1 + \Delta,\\
\sigma_k(t - \Delta) + \Delta = \sigma_k(t_1) + \Delta, &
t_1 +\Delta \leq t \leq t_2 + \Delta,\\
\sigma_k(t), & t \geq t_2 + \Delta;
\end{array}
\right.\\
&\sigma^a_{j}(t) = \left\{
\begin{array}{ll}
\sigma_j(t), & t \leq t_1,\\
\sigma_j(t_1), & t_1 \leq t \leq t_1 + \Delta,\\
\sigma_j(t - \Delta), &
t_1 +\Delta \leq t \leq t_2 + \Delta,\\
\sigma_j(t), & t \geq t_2 + \Delta.
\end{array}
\right.
\end{align}
It is possible to see that these scheduling functions are continuous and
satisfy invariant~\eq{eq:all:resources:t}, which makes this set
a suitable candidate for optimality.

Substituting these values of $\sigma$ into~\eq{eq:main:sigma:shared}, we obtain
\begin{equation*}
\begin{split}
&E_u(\sigma^a_1,\ldots,\sigma^a_n) = \int_0^{t_1} \sjprod{j=1}{n}{t}\dt +\\
&\int_{t_1}^{t_1+\Delta}(1-F_k(\sigma_k(t_1) + (t-t_1)))
\sjprod{j\neq k}{}{t_1}\dt +\\
&\int_{t_1+\Delta}^{t_2+\Delta}(1-F_k(\sigma_k(t_1)+\Delta))
\sjprod{j\neq k}{}{t-\Delta}\dt +
\int_{t_2+\Delta}^{\infty}\sjprod{j=1}{n}{t}\dt=\\
& \int_0^{t_1} \sjprod{j=1}{n}{t}\dt +
\sjprod{j\neq k}{}{t_1}\int_{0}^{\Delta}(1-F_k(\sigma_k(t_1) + x))\dx+\\
&\int_{t_1}^{t_2}(1-F_k(\sigma_k(t_1)+\Delta))
\sjprod{j\neq k}{}{t}\dt +
\int_{t_2+\Delta}^{\infty}\sjprod{j=1}{n}{t}\dt.
\end{split}
\end{equation*}
Subtracting $\Eus$ given by~\eq{eq:main:sigma:shared} from
$E_u(\sigma^a_1,\ldots,\sigma^a_n)$, we get
\begin{equation}
\begin{split}
&\Eus - E_u(\sigma^a_1,\ldots,\sigma^a_n) = \\
&\int_{t_1}^{t_2}[(1-F_k(\sigma_k(t))) - (1-F_k(\sigma_k(t_1) + \Delta))]
\sjprod{j\neq k}{}{t}\dt +\\
&\int_{t_2}^{t_2+\Delta}\sjprod{j=1}{n}{t}\dt -
\sjprod{j\neq k}{}{t_1}\int_{0}^{\Delta}(1-F_k(\sigma_k(t_1) + x))\dx.
\label{eq:proof:org:active:1}
\end{split}
\end{equation}
Let us consider the first term of the last equation.
Since in the interval $[t_1,t_2]$ $\sigma_k(t) = \sigma_k(t_1)$,
in this interval
\begin{equation*}
\begin{split}
&(1-F_k(\sigma_k(t))) - (1-F_k(\sigma_k(t_1) + \Delta)) =
(1-F_k(\sigma_k(t_1))) - (1-F_k(\sigma_k(t_1) + \Delta)) =\\
&-\int_0^{\Delta}\diff{(1-F_k(\sigma_k(t_1) + x))} =
\int_0^\Delta f_k(\sigma_k(t_1) + x)\dx =
\int_0^\Delta h_k(\sigma_k(t_1) + x)(1-F_k(\sigma_k(t_1) + x))\dx.
\end{split}
\end{equation*}
Due to monotonicity of $h_k(\sigma_k)$ in $t_1$,
\begin{equation*}
\begin{split}
&(1-F_k(\sigma_k(t))) - (1-F_k(\sigma_k(t_1) + \Delta)) =\\
&\int_0^\Delta h_k(\sigma_k(t_1) + x)(1-F_k(\sigma_k(t_1) + x))\dx
> h_k(\sigma_k(t_1))\int_0^\Delta (1-F_k(\sigma_k(t_1) + x))\dx,
\end{split}
\end{equation*}
which leads to
\begin{equation}
\begin{split}
&\int_{t_1}^{t_2}[(1-F_k(\sigma_k(t))) - (1-F_k(\sigma_k(t_1) + \Delta))]
\sjprod{j\neq k}{}{t}\dt >\\
&h_k(\sigma_k(t_1))\int_0^\Delta (1-F_k(\sigma_k(t_1) + x))\dx
\int_{t_1}^{t_2}\sjprod{j\neq k}{}{t}\dt.
\label{eq:proof:org:active:2}
\end{split}
\end{equation}
Let us now consider the second term of~\eq{eq:proof:org:active:1}.
Since in the interval $[t_2,t_2+\Delta]$ only $A_k$ is active,
in this interval
\begin{equation*}
\sigma_j(t) = \left\{
\begin{array}{ll}
\sigma_j(t_2), & j\neq k,\\
\sigma_k(t_1) + (t-t_2), & j = k.
\end{array}
\right.
\end{equation*}
Thus,
\begin{equation}
\int_{t_2}^{t_2+\Delta}\sjprod{j=1}{n}{t}\dt =\\
\sjprod{j\neq k}{}{t_2}\int_{0}^{\Delta}(1-F_k(\sigma_k(t_1) + x))\dx.
\label{eq:proof:org:active:3}
\end{equation}
Substituting~\eq{eq:proof:org:active:2} and~\eq{eq:proof:org:active:3}
into~\eq{eq:proof:org:active:1}, we obtain
\begin{equation}
\begin{split}
&\Eus - E_u(\sigma^a_1,\ldots,\sigma^a_n)
> \int_0^\Delta (1-F_k(\sigma_k(t_1) + x))\dx\;\times\\
&\left[h_k(\sigma_k(t_1))\int_{t_1}^{t_2}\sjprod{j\neq k}{}{t}\dt+
\sjprod{j\neq k}{}{t_2}-
\sjprod{j\neq k}{}{t_1}\right].
\end{split}
\label{eq:proof:org:active:4}
\end{equation}

The proof for the second scenario, 
where $A_k$ is suspended for $\Delta$,
is similar. For this scenario, the scheduling functions $\sigma_k(t)$ and
$\sigma_j(t)$ for $j\neq k$ can be represented as follows:
\begin{align}
&\sigma^i_{k}(t) = \left\{
\begin{array}{ll}
\sigma_k(t), & t \leq t_1 - \Delta,\\
\sigma_k(t_1 - \Delta) = \sigma_k(t_1) - \Delta, & t_1 - \Delta \leq t \leq t_2 - \Delta,\\
\sigma_k(t_1 - \Delta) + (t-(t_2-\Delta)) = \sigma_k(t_1) + (t-t_2), &
t_2 -\Delta \leq t \leq t_2,\\
\sigma_k(t), & t \geq t_2;
\end{array}
\right.\\
&\sigma^i_{j}(t) = \left\{
\begin{array}{ll}
\sigma_j(t), & t \leq t_1 - \Delta,\\
\sigma_j(t + \Delta), & t_1 - \Delta \leq t \leq t_2 - \Delta,\\
\sigma_j(t_2), & t_2 -\Delta \leq t \leq t_2,\\
\sigma_j(t), & t \geq t_2.
\end{array}
\right.
\end{align}
As before, these scheduling functions are continuous and
satisfy invariant~\eq{eq:all:resources:t}.

Substituting $\sigma^i$ into~\eq{eq:main:sigma:shared}, we obtain
\begin{equation*}
\begin{split}
&E_u(\sigma^i_1,\ldots,\sigma^i_n) =
\int_0^{t_1-\Delta} \sjprod{j=1}{n}{t}\dt +\\
&\int_{t_1-\Delta}^{t_2-\Delta}(1-F_k(\sigma_k(t_1) - \Delta))
\sjprod{j\neq k}{}{t + \Delta}\dt +\\
&\int_{t_2-\Delta}^{t_2}(1-F_k(\sigma_k(t_1)+(t-t_2)))
\sjprod{j\neq k}{}{t_2}\dt +
\int_{t_2}^{\infty}\sjprod{j=1}{n}{t}\dt=\\
& \int_0^{t_1-\Delta} \sjprod{j=1}{n}{t}\dt +
\sjprod{j\neq k}{}{t_2}\int_{0}^{\Delta}(1-F_k(\sigma_k(t_1) - x))\dx+\\
&\int_{t_1}^{t_2}(1-F_k(\sigma_k(t_1)-\Delta))
\sjprod{j\neq k}{}{t}\dt +
\int_{t_2+\Delta}^{\infty}\sjprod{j=1}{n}{t}\dt.
\end{split}
\end{equation*}
Subtracting $\Eus$ given by~\eq{eq:main:sigma:shared} from
$E_u(\sigma^i_1,\ldots,\sigma^i_n)$, we get
\begin{equation}
\begin{split}
&\Eus - E_u(\sigma^i_1,\ldots,\sigma^i_n) = \\
&\int_{t_1}^{t_2}[(1-F_k(\sigma_k(t))) - (1-F_k(\sigma_k(t_1) - \Delta))]
\sjprod{j\neq k}{}{t}\dt +\\
&\int_{t_1-\Delta}^{t_1}\sjprod{j=1}{n}{t}\dt -
\sjprod{j\neq k}{}{t_2}\int_{0}^{\Delta}(1-F_k(\sigma_k(t_1) - x))\dx.
\label{eq:proof:org:idle:1}
\end{split}
\end{equation}
As in the first scenario, in the interval $[t_1,t_2]$
\begin{equation*}
\begin{split}
&(1-F_k(\sigma_k(t))) - (1-F_k(\sigma_k(t_1) - \Delta)) =
(1-F_k(\sigma_k(t_1))) - (1-F_k(\sigma_k(t_1) - \Delta)) =\\
&\int_{-\Delta}^0\diff{(1-F_k(\sigma_k(t_1) + x))} =
-\int_{-\Delta}^0 f_k(\sigma_k(t_1) + x)\dx =\\
&-\int_0^{\Delta} f_k(\sigma_k(t_1) - x)\dx =
-\int_0^\Delta h_k(\sigma_k(t_1) - x)(1-F_k(\sigma_k(t_1) - x))\dx.
\end{split}
\end{equation*}
Due to monotonicity of $h_k(\sigma_k)$ in $t_1$,
\begin{equation*}
\begin{split}
&(1-F_k(\sigma_k(t))) - (1-F_k(\sigma_k(t_1) - \Delta)) =\\
&-\int_0^\Delta h_k(\sigma_k(t_1) - x)(1-F_k(\sigma_k(t_1) - x))\dx
> -h_k(\sigma_k(t_1))\int_0^\Delta (1-F_k(\sigma_k(t_1) - x))\dx,
\end{split}
\end{equation*}
which leads to
\begin{equation}
\begin{split}
&\int_{t_1}^{t_2}[(1-F_k(\sigma_k(t))) - (1-F_k(\sigma_k(t_1) - \Delta))]
\sjprod{j\neq k}{}{t}\dt > \\
&-h_k(\sigma_k(t_1))\int_0^\Delta (1-F_k(\sigma_k(t_1) - x))\dx
\int_{t_1}^{t_2}\sjprod{j\neq k}{}{t}\dt.
\label{eq:proof:org:idle:2}
\end{split}
\end{equation}
The transformations for the second term of~\eq{eq:proof:org:idle:1}
are also similar to the previous scenario.
Since in the interval $[t_1-\Delta,t_1]$ only $A_k$ is active,
in this interval
\begin{equation*}
\sigma_j(t) = \left\{
\begin{array}{ll}
\sigma_j(t_1), & j\neq k,\\
\sigma_k(t_1) - (t_1 - t), & j = k.
\end{array}
\right.
\end{equation*}
Thus,
\begin{equation}
\int_{t_1-\Delta}^{t_1}\sjprod{j=1}{n}{t}\dt =\\
\sjprod{j\neq k}{}{t_1}\int_{0}^{\Delta}(1-F_k(\sigma_k(t_1) - x))\dx.
\label{eq:proof:org:idle:3}
\end{equation}
Substituting~\eq{eq:proof:org:idle:2} and~\eq{eq:proof:org:idle:3}
into~\eq{eq:proof:org:idle:1}, we obtain
\begin{equation}
\begin{split}
&\Eus - E_u(\sigma^i_1,\ldots,\sigma^i_n)
> \int_0^\Delta (1-F_k(\sigma_k(t_1) - x))\dx\;\times\\
&-\left[h_k(\sigma_k(t_1))\int_{t_1}^{t_2}\sjprod{j\neq k}{}{t}\dt+
\sjprod{j\neq k}{}{t_2}-
\sjprod{j\neq k}{}{t_1}\right].
\end{split}
\label{eq:proof:org:idle:4}
\end{equation}
By~\eq{eq:proof:org:active:4} and~\eq{eq:proof:org:idle:4},
\begin{equation}
\text{sign}(\Eus - E_u(\sigma^a_1,\ldots,\sigma^a_n)) =
-\text{sign}(\Eus - E_u(\sigma^i_1,\ldots,\sigma^i_n)),
\end{equation}
and therefore one of these scenarios leads to better schedule, which
contradicts the optimality of the original one.

The proof for the case where control does not return to $A_k$ at all
is exactly the same and is omitted here. Informally, it can be viewed as
replacing $t_2$ by $\infty$ in all the formulas above,
 and the results are the same.
same results.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Proof of Theorem~\ref{th:notime:model:equivalence}}
\label{proof:th:notime:model:equivalence}
The claim of the theorem is as follows:

\begin{em}
If no time cost is taken into account ($c = 1$), the model with shared 
resources under intensity control settings is equivalent to  the model
with independent processes under suspend-resume control settings.
Namely, given a suspend-resume solution for the model with independent
processes, we may reconstruct an intensity-based solution with the same cost
for the model with shared resources and vice versa.
\end{em}

\begin{proof}
Let $E^*_{shared}$ be the optimal value for the framework with shared
resources, and $E^*_{independent}$ be the optimal value for the framework
with independent processes. Since $c = 1$, the two problems minimize
the same expression
\begin{equation}
E_u(\sigma_1, \ldots, \sigma_n) =\int_0^\infty\left(\sum_{i=1}^n\sip\right)
\prod_{j=1}^n(1-F_j(\sj))\dt \rightarrow \min,
\label{eq:proof:notime:1}
\end{equation}
and each set $\{\sigma_i\}$ satisfying the resource sharing constraints
automatically satisfies the process independence constraints, we obtain
\[
E^*_{independent} \leq E^*_{shared}.
\]
Let us prove that
\[
E^*_{shared} \leq E^*_{independent}.
\]
Assume that a set of functions $\sigma_1, \sigma_2, \ldots, \sigma_n$
is an optimal solution for the problem with independent processes,
i.e.,
\[
E_u(\sigma_1, \ldots, \sigma_n) = E^*_{independent}.
\]
We want to construct a set of functions $\{\wsi\}$ satisfying the
resource sharing constrains, such that 
\[
E_u(\wsin{1}, \ldots, \wsin{n}) = E_u(\sigma_1, \ldots, \sigma_n).
\]

Let us consider a set of discontinuity points of $\sigma'_i$
\[
\calT = \{ t | \exists i: \sigma'_i(t-\epsilon) \neq \sigma'_i(t+\epsilon) \}.
\]
In our model this set is countable, and we can write it as a sorted
sequence $t_0 = 0 < t_1 < \ldots < t_k < \ldots$.
The expected schedule cost in this case will have a form
\[
E_u(\sigma_1, \ldots, \sigma_n) =
\sum_{j=0}^\infty E_{u_j}(\sigma_1, \ldots, \sigma_n),
\]
where
\[
E_{u_j}(\sigma_1, \ldots, \sigma_n) = \int_{t_j}^{t_{j+1}}
\left(\sum_{i=1}^n\sip\right)
\prod_{l=1}^n(1-F_l(\sigma_l))\dt.
\]

We want to construct the functions $\wsi$ incrementally.
For each time interval $[t_j,t_{j+1}]$ we define a corresponding
point $\wtime{j}$ and a set of functions $\wsin{i}$, such that
\[
\wEu{j}(\wsin{1}, \ldots, \wsin{n}) = 
\int_{\wtime{j}}^{\wtime{j+1}}
\left(\sum_{l=1}^n\wsin{l}'\right)
\prod_{l=1}^n(1-F_l(\wsin{l}))\dt =
E_{u_j}(\sigma_1, \ldots \sigma_n).
\]

Let us denote $\sigma_{ij} = \sigma_i(t_j)$ and $\wsin{ij} = \wsi(t_j)$.
At the beginning, $\wsin{i0} = 0$ for each $i$, and $\wtime{0} = 0$.
Assume now that we have $\wtime{j'}$ defined for $j' < j$, and 
$\wsi(t)$ defined on each interval $[\wtime{j'},\wtime{j'+1}]$.
Let us show how to define $\wtime{j}$ and $\wsin{j}$ on 
$[\wtime{j},\wtime{j+1}]$.

By definition of $t_j$, $k = \sum_{l=1}^n\sigma'_l(t)$
is a constant for $t\in [t_{j},t_{j+1}]$. Since $\{\sigma_i\}$ satisfy 
suspend-resume constraints, exactly $k \geq 1$ processes are
active in this interval, each with full intensity. Without loss of generality, 
the active processes are $A_1, A_2, \ldots, A_k$, and
\begin{eqnarray*}
&&E_{u_j}(\sigma_1, \ldots, \sigma_n) = 
k\int_{t_j}^{t_{j+1}}\prod_{l=1}^n(1-F_l(\sigma_l))\dt =\\
&&k\prod_{l=k+1}^n(1-F_l(\sigma_{lj}))
\int_{t_j}^{t_{j+1}}\prod_{l=1}^k(1-F_l(t - t_j + \sigma_{lj}))\dt =\\
&&k\prod_{l=k+1}^n(1-F_l(\sigma_{lj}))
\int_0^{t_{j+1} - t_j}\prod_{l=1}^n(1-F_l(x + \sigma_{lj}))\dx.
\label{eq:proof:notime:2}
\end{eqnarray*}

Let $\wtime{j+1} = \wtime{j} + k(t_{j+1} - t_j)$, and let us define $\wsi(t)$ 
on the segment $[\wtime{j},\wtime{j+1}]$ as follows:
\begin{equation}
\wsi(t) = 
\left\{
\begin{array}{ll}
(t - \wtime{j}) / k + \wsin{ij}, & \sigma'_i > 0 \; 
\mbox{for}\; t\in[t_j,t_{j+1}]\\
\wsin{ij}, & \mbox{otherwise}.
\end{array}
\right.
\end{equation}
In this case, on this segment
\[
\sum_{l=1}^n\wsi'(t) = 1,
\]
which means that the $\wsi$ satisfy the resource sharing constraints.
By definition,
\begin{equation}
\wtime{j+1}-\wtime{j} = k(t_{j+1}-t_j),
\label{eq:proof:notime:3}
\end{equation}
and therefore for processes active on $[t_j,t_{j+1}]$ we obtain
\[
\wsin{i,j+1} - \wsin{ij} = \frac{\wtime{j+1}-\wtime{j}}{k} =
t_{j+1} - t_j = \sigma_{i,j+1} - \sigma_{ij}.
\]
For processes idle on $[t_j,t_{j+1}]$ the same equality holds as well:
\[
\wsin{i,j+1} - \wsin{ij} = 0 = \sigma_{i,j+1} - \sigma_{ij},
\]
and since $\wsi(t) = 0$ we obtain the invariant
\begin{equation}
\wsin{ij} = \sigma_{ij}.
\label{eq:proof:notime:4}
\end{equation}
The average cost for the new schedules may be represented as
\begin{eqnarray*}
&& \wEu{j}(\wsin{1}, \ldots, \wsin{n}) = 
\int_{\wtime{j}}^{\wtime{j+1}}\left(\sum_{l=1}^n\wsin{l}'\right)
\prod_{l=1}^n(1-F_l(\wsin{l}))\dt =\\
&&\prod_{l=k+1}^n(1-F_l(\wsin{lj}))
\int_{\wtime{j}}^{\wtime{j+1}} 
\prod_{l=1}^k(1-F_l((t-\wtime{j})/k + \wsin{lj}))\dt.
\end{eqnarray*}
Substituting $x = (t - \wtime{j})/k$ and using~\eq{eq:proof:notime:2},
\eq{eq:proof:notime:3} and~\eq{eq:proof:notime:4}, we obtain
\begin{eqnarray*}
&& \wEu{j}(\wsin{1}, \ldots, \wsin{n}) = 
k\prod_{l=k+1}^n(1-F_l(\wsin{lj}))
\int_0^{(\wtime{j+1} - \wtime{j})/k} 
\prod_{l=1}^k(1-F_l(x + \wsin{lj}))\dx =\\
&& k\prod_{l=k+1}^n(1-F_l(\sigma_{lj}))\dt 
\int_0^{t_{j+1} - t_j} \prod_{l=1}^k(1-F_l(x + \sigma_{lj}))\dx =\\
&&E_{u_j}(\sigma_1, \ldots, \sigma_n).
\end{eqnarray*}

From the last equation, it immediately follows that
\begin{eqnarray*}
E_u(\wsin{1}, \ldots, \wsin{n}) =
\sum_{j=0}^\infty \wEu{j}(\wsin{1}, \ldots, \wsin{n}) =
\sum_{j=0}^\infty E_{u_j}(\sigma_1, \ldots, \sigma_n) =
E_u(\sigma_1, \ldots, \sigma_n),
\end{eqnarray*}
which completes the proof.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vskip 0.2in
%\bibliographystyle{sty/aaai}
\bibliographystyle{theapa}
\bibliography{finkelstein03a}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
testforispell

