hebookpresentedtothereaderisdevotedtotime-dependentscheduling.
TScheduling problems, in general, consist in the allocation of resources
over time in order to perform a set of jobs. Any allocation that meets
all requirements concerning the jobs and resources is called a feasible
schedule. The quality of a schedule is measured by a criterion function.
The aim of scheduling is to ?nd, among all feasible schedules, a
schedule that optimizes the criterion function. A solution to an
arbitrary scheduling problem consists in giving a polynomial-time
algorithm generating either an optimal schedule or a schedule that is
close to the optimal one, if the given scheduling problem has been
proved to be computationally intractable. The scheduling problems are
subject of interest of the scheduling theory, originated in mid-?fties
of the twentieth century. The theory has been developing dynamically and
new research areas constantly come into existence. The subject of this
book, ti- dependent scheduling, is one of such areas. In time-dependent
scheduling, the processing time of a job is variable and depends on the
starting time of the job. This crucial assumption allows us to apply the
scheduling theory to a broader spectrum of problems. For example, in the
framework of the time-dependent scheduling theory we may consider the
problems of repayment of multiple loans, ?re ?ghting and maintenance
assignments. In this book, we will discuss algorithms and complexity
issues concerning various time-dependent scheduling problems.
