New directions in machine scheduling

We explored several new directions in machine scheduling including bicriteria scheduling, extra-resource analysis, a new model of preemption, the k-client problem, and AND/OR linear programming.; First, we considered the problem of nonpreemptively scheduling jobs that arrive over time on one machine to simultaneously minimize both the makespan and the average completion time. Previous research focused on proving the existence of schedules that simultaneously approximate both criteria. We showed that optimal bicriteria schedules can be constructed in polynomial-time. By optimal, we mean that bicriteria schedules with a better bound for both criteria do not exist for some input instances.; Second, we applied extra-resource analysis to the load-balancing problem. Extra-resource analysis is a generalization of competitive analysis. Extra-resource analysis has been used to distinguish good and bad on-line algorithms whereas competitive analysis cannot. We used extra-resource analysis to derive a new type of result, namely a qualitative divergence between on-line and off-line load-balancing algorithms.; Third, we introduced a new model of preemption, the "preempt-decay" model. In this model, when a job is preempted, the work done on that job gradually decays and has to be processed again. This model is a generalization of both the preempt-repeat and the preempt-resume models. We compared the optimal solution among the three models in the one machine environment.; Fourth, we studied the k-client problem which combines the ideas of multi-threaded environment and location-dependent processing time. In a multi-threaded environment, there are multiple chains of jobs. Jobs in each chain must be processed in order. In the environment where the processing time is location-dependent, the time required to process a job depends on the distance between the job and the server. When the underlying metric space in the k-client problem is a line, the problem becomes the multi-threaded disk scheduling problem. We analyzed two online greedy algorithms for the k-client problem, derived lower bounds in the line and the clique metric spaces, and considered the special case when k = 2.; Finally, we introduced AND/OR linear programming which is a generalization of ordinary linear programming. We devised an optimization scheme for AND/OR linear programs that has a small running time in practice. We outlined the application of AND/OR linear programs to the problem of finding a lower bound instance for an approximation algorithm. We demonstrated the technique on the problem of nonpreemptively scheduling jobs that arrive over time on one machine to minimize the total completion time.