So Wai Kuen. / Year shown on spine: 1997. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 87-92). / INTRODUCTION --- p.1 / Chapter 1.1 --- Introduction to SLCR Problem --- p.1 / Chapter 1.2 --- Our Contributions --- p.1 / Chapter 1.3 --- Organization of the thesis --- p.3 / LITERATURE REVIEW --- p.4 / Chapter 2.1 --- Research in the Capacitated Resource Constraint Problem --- p.4 / Chapter 2.2 --- The Single Level Constrained Resource Problem --- p.5 / Chapter 2.3 --- The Multiple Level Constrained Resource Problem --- p.8 / Chapter 2.4 --- Research in the Fixed Charge Problem --- p.9 / Chapter 2.4.1 --- Approximate Methods --- p.9 / Chapter 2.4.2 --- Exact Methods --- p.10 / Chapter 2.5 --- Conclusion --- p.11 / THE SLCR PROBLEM WITH BACKORDERING --- p.12 / Chapter 3.1 --- Problem Description and Formulation --- p.13 / Chapter 3.2 --- Description of the heuristic --- p.19 / Chapter 3.2.1 --- Phase I --- p.19 / Chapter 3.2.2 --- Phase II --- p.26 / Chapter 3.3 --- Design of Computational Experiments --- p.30 / Chapter 3.3.1 --- Specifications of test problems ( 3 products and 12 period case ) --- p.31 / Chapter 3.3.2 --- Computation of the Lower Bound --- p.38 / Chapter 3.4 --- Computational Results --- p.39 / Chapter 3.5 --- Comparison to Millar and Yang's Algorithm --- p.48 / Chapter 3.5.1 --- Comparison Results --- p.49 / Chapter 3.6 --- Conclusion --- p.50 / THE OPTIMIZATION BASED ALGORITHM --- p.51 / Chapter 4.1 --- The Formulation --- p.52 / Chapter 4.2 --- The Algorithm --- p.60 / Chapter 4.2.1 --- Phase I --- p.60 / Chapter 4.2.2 --- Phase II --- p.63 / Chapter 4.2.3 --- Phase III --- p.70 / Chapter 4.3 --- An Illustrative Example --- p.72 / Chapter 4.4 --- Computational Results --- p.79 / Chapter 4.5 --- Conclusion --- p.84 / CONCLUSION --- p.85 / BIBLIOGRAPHY --- p.87

To date, group scheduling research has primarily focused on examining the performance of different group heuristics under various experimental conditions. However, the dynamic selection of group heuristics has not received sufficient attention from researchers. The objective of this paper is to demonstrate a mechanism for the dynamic selection of group heuristics from several candidate alternatives by exploiting real time information from the Flexible Manufacturing System (FMS). In this regard, two tools, viz., Analytic Hierarchy Process (AHP) and Simple Multi-Attribute Rating Technique Exploiting Ranks (SMARTER), are used to develop models for part type and family selection. The experimental results indicate that the performance of the proposed models are better than the common group scheduling heuristics under varied experimental conditions. / Singapore-MIT Alliance (SMA)

Two methods of obtaining approximate solutions to the classic General Job-shop Scheduling Program are investigated. The first method is iterative. A sampling of the solution space is used to decide which of a collection of space pruning constraints are consistent with "good" schedules. The selected space pruning constraints are then used to reduce the search space and the sampling is repeated. This approach can be used either to verify whether some set of space pruning constraints can prune with discrimination or to generate solutions directly. Schedules can be represented as trajectories through a Cartesian space. Under the objective criteria of Minimum maximum Lateness family of "good" schedules (trajectories) are geometric neighbors (reside with some "tube") in this space. This second method of generating solutions takes advantage of this adjacency by pruning the space from the outside in thus converging gradually upon this "tube." One the average this methods significantly outperforms an array of the Priority Dispatch rules when the object criteria is that of Minimum Maximum Lateness. It also compares favorably with a recent relaxation procedure.

Multi-hop wireless mesh networks (WMNs) provide a cost-effective means to enable broadband wireless access (BWA) services to end users. Such WMNs are required to support different classes of traffic where each class requires certain quality of service (QoS) levels. The research direction undertaken in this thesis considers the development of enhanced routing and scheduling algorithms that enable WMNs to support various QoS metrics for the served traffic. A fundamental class of routing problems in WMNs asks whether a given end-to-end flow that requires certain bandwidth, and benefits from routing over a single path (also called non-bifurcated routing), can be routed given that some ongoing flows are being served in the network. In the thesis, we focus on the development of combinatorial algorithms for solving such incremental non-bifurcated problems for two types of WMNs: 1. WMNs where mesh routers use contention-based protocol for medium access control (MAC), and 2. WMNs where mesh routers use time division multiple access (TDMA) for MAC. For WMNs employing contention-based MAC protocols, we present a novel non-bifurcated routing algorithm that employs techniques from the theory of network flows. The main ingredient in our algorithm is a method for computing interference-constrained flow augmenting paths for routing subscriber demands in the network. For WMNs employing TDMA, we develop a number of joint routing and scheduling algorithms, and investigate the use of such algorithms to maximize the number of served flows. In chapter 4, we consider a throughput maximization problem in the well-known class of grid WMNs. We present an iterative algorithm that strives to achieve high throughput by considering routing and scheduling a pair of distinct flows simultaneously to the gateway in each iteration. In chapter 5, we explore joint routing and scheduling in TDMA-based WMNs with arbitrary topologies, and devise an algorithm that can deal with arbitrary interference relations among pairs of transmission links. In particular, our devised algorithm solves a generalized problem where a cost value is associated with using any possible time-slot on any transmission link, and a minimum cost route is sought along which a new flow can be scheduled without perturbing existing slot assignments.

Globalization and containerization have changed the shipping industry and carriers are challenged to reshape their operational planning in order to maintain their market share. The objective of this paper is to formulate a model to determine the optimal fleet size and sailing frequency that minimizes total shipping and inventory (wait) costs for a container shipping company. The proposed model assumes an arrival process that follows a Poisson rate. We first consider unlimited ship capacity and propose a solution to determine the required fleet size and the optimal sailing frequency. We then extend the work to consider limited ship capacity. Furthermore, we introduce a cost component associated with outsourcing shipments due to insufficient capacity. The outsourced shipment is utilized when the number of containers at a port exceeds the available capacity. In the general case, a closed form solution could not be derived. Therefore, a simulation study is undertaken to analyze optimal fleet sizing, scheduling, and outsourcing policies under varying paramaters. Our study investigates the trade-off between building capacity and outsourcing in the context of cargo shipment. The model proves to be a reliable tool to determine optimal delay time at ports and optimal fleet size.

Thesis (Ph. D.)--University of Texas at Austin, 2006. / Vita. Includes bibliographical references.

Thesis (Ph. D.)--University of Hong Kong, 2006. / Title proper from title frame. Also available in printed format.

Battery-powered portable embedded systems have been widely used in many applications. These embedded systems have to concurrently perform a multitude of complex tasks under stringent time constraints. As these systems become more complex and incorporate more functionality, they became more power-hungry. Thus, reducing power consumption and extending battery lifespan while guaranteeing the timing constraints has became a critical aspect in designing such systems. This gives rise to three aspects of research: (i) Guaranteeing the execution of the hard real-time tasks by their deadlines, (ii) Determining the minimum voltage under which each task can be executed, and (iii) Techniques to take advantage of run-time variations in the execution times of tasks. In this research, we present techniques that address the above aspects in single and multi processor embedded systems. We study the performance of the proposed techniques on various benchmarks in terms of energy savings.

Time-sensitive applications that are also CPU intensive like video games, video playback, eye-candy desktops etc. are increasingly common. These applications run on commodity operating systems that are targeted at diverse hardware, and hence they cannot assume that sufficient CPU is always available. Increasingly, these applications are designed to be adaptive. When executing multiple such applications, the operating system must not only provide good timeliness but also (optionally) allow co-ordinating their adaptations so that applications can deliver uniform fidelity. In this work, we present a starvation-free, fair, process scheduling algorithm that provides predictable and low latency execution without the use of reservations and assists adaptive time sensitive tasks with achieving consistent quality through cooperation. We combine an event-driven application model called cooperative polling with a fair-share scheduler. Cooperative polling allows sharing of timing or priority information across applications via the kernel thus providing good timeliness, and the fair-share scheduler provides fairness and full utilization. Our experiments show that cooperative polling leverages the inherent efficiency advantages of voluntary context switching versus involuntary pre-emption. In CPU saturated conditions, we show that the scheduling responsiveness of cooperative polling is five times better than a well-tuned fair-share scheduler, and orders of magnitude better than the best-effort scheduler used in the mainstream Linux kernel.

The coverage and energy issues are the fundamental problems which prevent the development of wireless sensor networks. In order to accurately evaluate the monitoring quality (coverage), one needs to model the interactive of sensors, phenomenons and the environment. Furthermore, in collaborative with scheduling algorithm and computer optimization, protocols can improve the overall monitoring quality and prolong the lifetime of network. This thesis is an investigation of coverage problem and its relative applications in the wireless sensor networks. We first discuss the realistic of current boolean sensing model and propose an irregular sensing model used to determine the coverage in the area with obstacles. We then investigate a joint problem of maintaining the monitoring quality and extending the lifetime of network by using scheduling schemes. Since the scheduling problem is NP hard, genetic algorithm and Markov decision process are used to determine an achievable optimal result for the joint problem of coverage-preserving and lifetime-prolong. In order to avoid the cost of centralized or distributed scheduling algorithms, a localized coverage-preserving scheduling algorithm is proposed by exploring the construction process of Voronoi diagram. Besides exploring the coverage characteristic in a static wireless sensor network, we investigate the coverage problem when the mobile elements are introduced into network. We consider the single-hop mobile data gathering problem with the energy efficiency and data freshness concerns in a wireless sensor network where the connectivity cannot be maintained. We first investigate the upper/lower bound of the covering time for a single collector to cover the monitoring area. Through our investigation we show that for a bounded rectangle area a hexagon walk could explore the area more efficiently than a random walk when the edges of area are known. We then propose a virtual force mobile model (VFM) in which the energy consumption for data transmission is modeled as a virtual elastic force and used to guide of mobile collectors to move to optimal positions for energy saving.