This dissertation addresses the problem of scheduling a set of jobs under two different measures of performance: total tardiness and weighted number of tardy jobs. A new solution approach is presented for the single-machine tardiness problem. This views the problem as one of determining an optimal partition of the job set into early and tardy subsets. The scheme is validated by the development of necessary conditions for optimality. It is shown that if an optimal partition of the jobs into early and tardy subsets is given, the conditions are not only necessary but also sufficient. These results are used to derive a polynomial algorithm to generate a sequence that satisfies these conditions for any arbitrary partition. The implications of these results with respect to solving the tardiness problem, as well as some other related problems, are examined. Particular emphasis is placed on the impact of the partition approach as a device to enhance the performance of existing branch-and-bound procedures. The use of this approach to generate valid inequalities is also discussed. The problem of scheduling a single machine to minimize the weighted number of tardy jobs is examined in detail. A new branch-and-bound procedure is presented as well as the first extensive computational study of the problem. The proposed algorithm relies on lower bounds obtained by means of two relaxations of the problem for which efficient solution procedures exist. The merits of both bounding schemes are extensively tested. The computational results indicate that exact solutions for large problems can be obtained in just a few seconds of computer time. The efficacy of the approach as a heuristic method is also verified. Further, the computational experience provides insight into how various problem parameters affect the solution difficulty of particular problem instances. The multiple-processor version of the weighted number of tardy jobs model is also considered. The basic algorithmic framework for the single-machine problem is extended to obtain optimal preemptive schedules for parallel machines, which may be identical, uniform, or unrelated.

Online flow-time scheduling is a fundamental problem in computer science and has been extensively studied for years. It is about how to design a scheduler to serve computer jobs with unpredictable arrival times and varying sizes and priorities so as to minimize the total flow time (better understood as response time) of jobs. It has many applications, most notable in the operating of server farms. As energy has become an important issue, the design of scheduler also has to take power management into consideration, for example, how to scale the speed of the processors dynamically. The objectives are orthogonal as one would prefer lower processor speed to save energy, yet a good quality of service must be retained. In this thesis, I study a few scheduling problems for energy and flow time in depth and give new algorithms to tackle them. The competitiveness of our algorithms is guaranteed with worst-case mathematical analysis against the best possible or hypothetical solutions. In the speed scaling model, the power of a processor increases with its speed according to a certain function (e.g., a cubic function of speed). Among all online scheduling problems with speed scaling, the nonclairvoyant setting (in which the size of a job is not known during its execution) with arbitrary priorities is perhaps the most challenging. This thesis gives the first competitive algorithm called WLAPS for this setting. In reality, it is not uncommon that during the peak-load period, some (low-priority) users have their jobs rejected by the servers. This triggers me to study more complicated scheduling algorithms that can strike a good balance among speed scaling, flow time and rejection penalty. Two new algorithms UPUW and HDFAC for different models of rejection penalty have been proposed and analyzed. Last, but perhaps the most interesting, we study power management in large server farm environment in which the primary energy saving mechanism is to put some processors to sleep. Two new algorithms POOL and SATA have been designed to tackle jobs that cannot and can migrate among the processors, respectively. They are integrated algorithms that can consider speed scaling, job scheduling and processor sleep management together to optimize the energy usage and ow time simultaneously. These algorithms are again proven mathematically to be competitive even in the worst case. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

by Hoi Wing, Yung. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 56-60). / Abstracts in English and Chinese. / List of Figures --- p.v / List of Tables --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Literature Review --- p.3 / Chapter 1.2.1 --- On the Fixed Multiprocessor Job Scheduling Problems --- p.6 / Chapter 1.2.2 --- On the Nonfixed Multiprocessor Job Scheduling Problems --- p.8 / Chapter 1.3 --- Problem Formulation --- p.12 / Chapter 1.4 --- Organization of the Thesis --- p.13 / Chapter 2 --- Genetic Algorithms --- p.15 / Chapter 2.1 --- Basic Concepts --- p.15 / Chapter 2.2 --- Main components --- p.17 / Chapter 3 --- A New Genetic Algorithm --- p.24 / Chapter 3.1 --- Coding --- p.25 / Chapter 3.1.1 --- Simple Example --- p.28 / Chapter 3.2 --- Similarity of Chromosomes --- p.30 / Chapter 3.3 --- Fitness Evaluation --- p.33 / Chapter 3.4 --- Configurations --- p.35 / Chapter 3.4.1 --- Parent Selection --- p.35 / Chapter 3.4.2 --- Multipoint Crossover --- p.36 / Chapter 3.4.3 --- Multipoint Mutation --- p.38 / Chapter 3.4.4 --- Replacement Step --- p.38 / Chapter 3.4.5 --- Termination Criterion --- p.39 / Chapter 4 --- Experimental Results --- p.41 / Chapter 4.1 --- Total Weighted Completion Time --- p.41 / Chapter 4.1.1 --- Lee and Cai's Algorithm --- p.42 / Chapter 4.1.2 --- Computational Results --- p.44 / Chapter 4.1.3 --- On the Problem of Minimizing the Total Completion Time --- p.46 / Chapter 4.2 --- Makespan --- p.48 / Chapter 4.2.1 --- Mahesh's Algorithms and Linn & Chen's Algorithm --- p.48 / Chapter 4.2.2 --- Computational Results --- p.52 / Chapter 5 --- Conclusion --- p.54 / Bibliography --- p.56

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

No description available.

No description available.

Traditional critical path methods imply the assumption of unlimited availability of resources. Mathematical models and heuristic techniques are two alternatives that consider resource limitation to sequence the activities of a project. This research explores the consideration of project scheduling under resource constraints for the specific case of single resource, single project scheduling. A computer model called GENRES-II search model is developed using a modification of Brooks' algorithm to develop project schedules. The criteria used are various weighted combinations of ACTIM, ACTRES and ACTFOL. An improvement of GENRES-II solutions is obtained when the best set of GEN-II values is input to a computer model called COMSOAL simulation model. The criteria developed generates a large number of feasible solutions rapidly. The probability of generating optimal solutions is related to the size of the generated sample. Eight network cases were considered to validate both computer models. Special attention was given to those activities that were considered critical at a specific time. The number of resources available was increased to a new higher limit in order to schedule activities that became critical. The GENRES-II model was effective in finding project durations equal to or less than ACTIM, ACTRES, GENRES or ACTFOL. The COMSOAL model was found very effective in most of the cases in improving the GEN-II solutions.

published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

by Wong Tin-Lam. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 70-73). / Abstract --- p.ii / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Scheduling Problems --- p.1 / Chapter 1.2 --- Literature Review --- p.4 / Chapter 1.2.1 --- Sized Multiprocessor Task Scheduling --- p.5 / Chapter 1.2.2 --- Fixed Multiprocessor Task Scheduling --- p.6 / Chapter 1.2.3 --- Set Multiprocessor Task Scheduling --- p.8 / Chapter 1.3 --- Organization of Thesis --- p.10 / Chapter 2 --- Overview --- p.11 / Chapter 2.1 --- Machine Environment --- p.11 / Chapter 2.2 --- The Jobs and Their Requirements --- p.12 / Chapter 2.3 --- Assumptions --- p.13 / Chapter 2.4 --- Constraints --- p.14 / Chapter 2.5 --- Objective --- p.15 / Chapter 2.6 --- An Illustrative Example --- p.17 / Chapter 2.7 --- NP-Hardness --- p.20 / Chapter 3 --- Methodology --- p.22 / Chapter 3.1 --- Dynamic Programming --- p.22 / Chapter 3.1.1 --- Problem Analysis --- p.24 / Chapter 3.2 --- Key Idea to solve the problem --- p.27 / Chapter 3.3 --- Algorithm --- p.28 / Chapter 3.3.1 --- Phase 1 --- p.28 / Chapter 3.3.2 --- Phase 2 --- p.37 / Chapter 4 --- Extensions --- p.46 / Chapter 4.1 --- "Polynomially Solvable Cases P2 --- p.46 / Chapter 4.1.1 --- Dynamic Programming --- p.47 / Chapter 4.2 --- "Set Problem P2/setj,prmp/TmaX" --- p.55 / Chapter 4.2.1 --- Processing times for set jobs --- p.56 / Chapter 4.2.2 --- Algorithm --- p.58 / Chapter 4.3 --- k´ؤMachine Problem with only two types of jobs --- p.64 / Chapter 5 --- Conclusion and Future Work --- p.67 / Chapter 5.1 --- Conclusion --- p.67 / Chapter 5.2 --- Some Future Work --- p.68 / Bibliography --- p.70

Thesis (B.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Bibliography: leaf 54. / by Paul Alan Roush. / B.S.