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

Not available

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.

No description available.

No description available.

No description available.

No description available.

No description available.