Thesis--PlanB (M.S.)--University of Wisconsin--Stout, 2003. / Includes bibliographical references.

Thesis (Ph. D.)--Ohio State University, 2003. / Title from first page of PDF file. Document formatted into pages; contains xiii, 97 p.: ill. (some col.). Includes abstract and vita. Advisor: Kevin M. Passino, Dept. of Electrical Engineering. Includes bibliographical references (p. 94-97).

Thesis PlanB (M.S.)--University of Wisconsin--Stout, 2009. / Includes bibliographical references.

Construction Projects involve a large number of participants with often overlapping activities. Schedules play a key role in coordination of these activities. A general contractor or a construction manager is usually responsible for coordination and has a master schedule that covers the scope of the entire project. The individual participants have different project management objectives and build schedules for their scope of work using different breakdown structures, different levels of detail, different scheduling software and different naming conventions. Existing scheduling techniques and software provide a robust set of constructs to generate these individual schedules. However, coordination of these schedules is a manual iterative task not adequately supported by existing theories and software tools. The primary aim of this research was to provide a framework to enable analysis across distributed heterogeneous schedules. The framework presented in this dissertation, schedule mappings, provides a set of constructs to dynamically link individual participant schedules to the master schedule. The schedule mappings approach uses the linked schedules to facilitate schedule coordination by rapid identification of scheduling conflicts. This identification enables rapid initial coordination of schedules and supports assessment of scheduling alternatives in response to a schedule change. A software tool was developed using Microsoft Visual Basic[trademark] programming language as a Shared Addin for Microsoft Project[trademark]. This dissertation contributes to state of the art of scheduling by providing a framework for reasoning across multiple schedules. From an industry perspective, this research makes a contribution by formalizing identification of scheduling conflicts. The formalisms and the tool should help industry professionals in rapid assessment of scheduling alternatives. The tool enabled the use of the schedule mappings approach by industry professionals and was used for validation. The approach was validated in a two step process and was shown to be beneficial. / text

This thesis presents several new results on online job scheduling. Job scheduling is a basic requirement of many practical computer systems, and the scheduling behavior directly affects a system’s performance. In theoretical aspect, scheduling scenarios are abstracted into scheduling models, which are studied mathematically. In this thesis, we look into a variety of scheduling models which are under active research. We incorporate these models and organize them into generalized pictures. We first study non-clairvoyant scheduling to minimize weighted flow time on two different multi-processor models. In the first model, processors are all identical and jobs can possibly be speeded up by running on several processors in parallel. Under the non-clairvoyant model, the online scheduler has no information about the actual job size and degree of speed-up due to parallelism during the execution of a job, yet it has to determine dynamically when and how many processors to run the jobs. The literature contains several O(1)-competitive algorithms for this problem under the unit-weight multi-processor setting [13, 14] as well as the weighted single-processor setting [5]. This thesis shows the first O(1)-competitive algorithm for weighted flow time in the multi-processor setting. In the second model, we consider processors with different functionalities and only processors of the same functionality can work on the same job in parallel to achieve some degree of speed up. Here a job is modeled as a sequence of non-clairvoyant demands of different functionalities. This model is derived naturally from the classical job shop scheduling; but as far as we know, there is no previous work on scheduling to minimize flow time under this multi-processor model. In this thesis we take a first step to study non-clairvoyant scheduling on this multi-processor model. Motivated by the literature on 2-machine job shop scheduling, we focus on the special case when processors are divided into two types of functionalities, and we show a non-clairvoyant algorithm that is O(1)-competitive for weighted flow time. This thesis also initiates the study of online scheduling with rejection penalty in the non-clairvoyant setting. In the rejection penalty model, jobs can be rejected with a penalty, and the user cost of a job is defined as the weighted flow time of the job plus the penalty if it is rejected before completion. Previous work on minimizing the total user cost focused on the clairvoyant single-processor setting [3, 10] and has produced O(1)-competitive online algorithm for jobs with arbitrary weights and penalties. This thesis gives the first non-clairvoyant algorithms that are O(1)-competitive for minimizing the total user cost on a single processor and multi-processors, when using slightly faster (i.e., (1 + ∈)-speed for any ∈> 0) processors. Note that if no extra speed is allowed, no online algorithm can be O(1)-competitive even for minimizing (unweighted) flow time alone. The above results assume a processor running at a fixed speed. This thesis shows more interesting results on extending the above study to the dynamic speed scaling model, where the processor can vary the speed dynamically and the rate of energy consumption is an arbitrary increasing function of speed. A scheduling algorithm has to decide job rejection and determine the order and speed of job execution. It is interesting to study the tradeoff between the above-mentioned user cost and energy. This thesis gives two O(1)-competitive non-clairvoyant algorithms for minimizing the user cost plus energy on a single processor and multi-processors, respectively. / published_or_final_version / Computer Science / Master / Master of Philosophy

Job scheduling, which greatly impacts on the system performance, is a fundamental problem in computer science. In this thesis, we study three kinds of scheduling problems, that is, deadline scheduling, due date scheduling, and flow time scheduling. Traditionally, the major concern for scheduling problems is the system performance, i.e. the “Quality of Service" (QoS). Different scheduling problems use different QoS measurements. For deadline scheduling, the most common QoS to optimize is the throughput; for due date scheduling, it is the total quoted lead time; and for flow time scheduling, it is the total (weighted) flow time. Recently, energy efficiency is becoming more and more important. Many modern processors adopt technologies like dynamic speed scaling and sleep management to reduce energy usage. Much work is done on energy efficient scheduling. In this thesis, we study this topic for all three kinds of scheduling mentioned above. Meanwhile, we also revisit the traditional flow time scheduling problem to optimize the QoS. However, we consider the problem in a more realistic model that makes the problem much more challenging. Below is the summary of the problems studied in the thesis. First, we consider the tradeoff between energy and throughput for deadline scheduling. Specifically, each job is associated with a value (or importance) and a deadline. A scheduling algorithm is allowed to discard some of the jobs, and the objective is to minimize total energy usage plus total value of discarded jobs. When processor's maximum speed is unbounded, we propose an O(1)-competitive algorithm. When processor's maximum speed is bounded, we show a strong lower bound and give an algorithm with a competitive ratio close to that lower bound. Second, we study energy efficient due date scheduling. Jobs arrive online with different sizes and weights. An algorithm needs to assign a due date to each job once it arrives, and complete the job by the due date. The quoted lead time of a job equals its due date minus its arrival time, multiplied by its weight. We propose a competitive algorithm for minimizing the sum of the total quoted lead time and energy usage. Next, we consider flow time scheduling with power management on multiple machines. Jobs with arbitrary sizes and weights arrive online. Each machine consumes different amount of energy when processing a job, idling or sleeping. A scheduler has to maintain a good balance of the states of the machines to avoid energy wastage and, meanwhile, guarantee high QoS. Our result is an O(1)-competitive algorithm to minimize total weighted flow time plus energy usage. Finally, we consider the traditional preemptive scheduling to minimize total flow time. Previous theoretical results often assume preemption is free, which is not true for most systems. We investigate the complexity of the problem when a processor has to perform a certain amount of overhead before it resumes the execution of a job preempted before. We first show an Ω(n^(1/4)) lower bound, and then, propose a (1+ε)-speed (1+ 1/ε )-competitive algorithm in resource augmentation model. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

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

Not available / text

Within manufacturing, increasing interest in being placed in the possibilities of integrated process planning and scheduling. Separating these two related tasks can impose constraints, on the final schedule, which are both undesirable and unnecessary. These constraints arise from premature decisions regarding the allocation of manufacturing resources. By making use of flexible process plans, these decisions can be delayed until the most appropriate time: during scheduling. The decisions can then be made on the basis of objectives common to both tasks (such as the minimisation of manufacturing cost). This thesis outlines an approach to manufacturing planning which is based on a highly general formulation of the problem. This integrated process planning/scheduling problem can be viewed as a generalisation of process plan optimisation, a task which is also considered in detail. A novel approach to plan optimisation is proposed, which in turn forms the basis for integrated planning and scheduling. Some research into integrated planning/scheduling has been reported in the literature. However, researchers differ in the way they formulate the integrated task. This thesis therefore attempts to outline a general framework for the characterisation of integrated process planning and scheduling problems. This considers both the degree and representation of process plan flexibility, and also the level of detail at which the shop floor is modelled. This framework forms a basis for a comparison of solution approaches. Published solution approaches are mostly based on the use of dispatching rules, but attempts have been made to use optimal search. The use of dispatching rules is essentially an ad hoc approach and, although relatively easy to apply in practice, produces solutions of mediocre quality. However, new research using simulated annealing suggests that neighbourhood search may offer a valuable alternative. This observation is supported by ambitious research published on the use of genetic algorithms. Because of the extreme combinatorial complexity of the combined task, optimal search methods are unlikely to be usable in practice. Furthermore, such methods exhibit a severe lack of generality because they make highly specific assumptions about problem formulation. Neighbourhood search techniques have inherent properties which give them a much higher level of generality. Although it is not an optimal search method, simulated annealing has been shown to provide solutions of significantly higher quality than those achieved by dispatching rule techniques. Also, and unlike optimal search techniques, it appears able to handle the immense complexity of the integrated planning/scheduling task. For the above reasons, it is argued that neighbourhood search techniques, such as simulated annealing, provide the best compromise available between solution quality and practical applicability.

The majority of the commercially available systems developed for capacity planning have been designedf or organisationsw hich are involved with make-to-stockm anufacturingT. heses ystemsa re difficult to implementi n bespokem anufacturing( make-to-ordero) rganisationss ince they are unable to accommodateth e requirementso f the volatile productione nvironment. This thesisi dentifies the uniqueo peratingc haracteristicos f the manufacturinge nvironmenta ssociated with bespokem anufacturingw hich caused ifficulty with the implementationo f commerciallya vailable systemsT. he findings from this investigationa re usedt o formulatea design for a capacityp lanning systemw hich fulfils the unique requirementso f the bespokem anufacturinge nvironment. The proposed system executes the capacity planning function at two separate levels of detail by integrating rough cut capacity planning with finite capacity planning. The two planning mechanisms are also integrated with a shop floor data collection system which has been designed for the assembly environment. Data interaction is achieved between the capacity planning modules and the shop floor data collection system via an Interface ManagemenSt ystem which ensurest hat the scheduled ata containedi n the individual systemsr emainsi n synchronisationa t all times. The capacity planning system also includes the design and development of a large scale display facility which is able to accommodateth e large volume of scheduled ata required to be viewed for finite capacity planning. This facility has been designed using multiple co-ordinated screens which are linked by a local area network. A data interface and parallel processing facility is incorporated in the design which enable the processing of a software application to be distributed over multiple nodes.