| Traditional scheduling research focuses on problems with a single objective. However, in practice a schedule is often judged by more than one criterion. For instance, the interests of customers are usually not taken into account in low-cost production strategies. Managers often have to juggle schedules in order to satisfy customers without increasing cost. For this reason, problems with multiple objectives are becoming popular in scheduling research.; In the thesis, we consider two single-machine scheduling problems with dual objective functions. The first problem is a classical double-objective problem. The objectives considered are maximum tardiness and the number of late jobs. We present a branch-and-bound algorithm for the problem with fixed maximum tardiness. We also suggest extensions of this algorithm in order to compute the complete trade-off curve of the two objectives.; The second problem belongs to another relatively new direction in scheduling research, namely, scheduling with controllable processing times. Here, processing times of jobs are not fixed and can be compressed. We assume that this compression incurs a linear cost, which is included in the objective. The main objective is the number of late jobs. We prove that this problem is NP-hard, present a pseudo-polynomial dynamic programming algorithm, and also consider three special cases which are solvable in polynomial time.; We also discuss applications of scheduling theory. We present a classification of scheduling systems, discuss the requirements for each class, and present examples. Special attention is paid to a module for designing custom algorithms. Such a module can be very useful in an educational scheduling system; however, it is not present in most existing systems.; Last, we present an educational scheduling system called LEKIN. We designed LEKIN for teaching Scheduling and Operation Management courses. The system can be also used as a tool for algorithm design. |
