Yip Ka-yun. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 107-113). / Abstract also in Chinese. / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview --- p.1 / Chapter 1.2 --- Our Contributions --- p.2 / Chapter 1.3 --- Organization of the Thesis --- p.4 / Chapter Chapter 2 --- Literature Review --- p.5 / Chapter 2.1 --- Overview --- p.5 / Chapter 2.2 --- Research in Capacitated Lot Sizing Problem without significant setup times --- p.5 / Chapter 2.3 --- Research in Capacitated Lot Sizing Problem with setup time consideration --- p.12 / Chapter 2.4 --- Summary --- p.15 / Chapter Chapter 3 --- Capacitated Lot Sizing Problem with Setup Times --- p.16 / Chapter 3.1 --- Overview --- p.16 / Chapter 3.2 --- Problem Description and Formulation --- p.20 / Chapter 3.2.1 --- Our problem formulation / Chapter 3.2.2 --- Comparison between our problem formulation and traditional problem formulation / Chapter 3.3 --- Description of the Algorithm --- p.26 / Chapter 3.3.1 --- Wagner-Whitin algorithm / Chapter 3.3.2 --- Transportation problem / Chapter 3.3.3 --- Consistence test / Chapter 3.3.4 --- Subgradient optimization / Chapter 3.3.5 --- Computation of lower bound / Chapter 3.4 --- Design of Experiment --- p.43 / Chapter 3.4.1 --- Product demands / Chapter 3.4.2 --- Setup costs / Chapter 3.4.3 --- Setup times / Chapter 3.4.4 --- Capacity costs / Chapter 3.4.5 --- Inventory holding costs / Chapter 3.4.6 --- Quantity of capacity available for production / Chapter 3.4.7 --- Capacity absorption rate / Chapter 3.4.8 --- Generation of larger problems / Chapter 3.4.9 --- Initialization of Lagrangean multipliers / Chapter 3.4.10 --- Close test / Chapter 3.5 --- Open test --- p.58 / Chapter 3.6 --- Managerial Implications --- p.61 / Chapter 3.7 --- Summary --- p.61 / Chapter Chapter 4 --- Capacitated Lot Sizing Problem without Setup Times --- p.63 / Chapter 4.1 --- Overview --- p.63 / Chapter 4.2 --- Problem Description and Formulation --- p.64 / Chapter 4.3 --- Description of the Algorithm --- p.67 / Chapter 4.3.1 --- Decomposition scheme / Chapter 4.3.2 --- Wagner-Whitin algorithm / Chapter 4.3.3 --- Transportation problem / Chapter 4.3.4 --- Subgradient optimization / Chapter 4.3.5 --- Computation of lower bound / Chapter 4.4 --- Design of Experiment --- p.80 / Chapter 4.4.1 --- Product demands / Chapter 4.4.2 --- Setup costs / Chapter 4.4.3 --- Capacity costs / Chapter 4.4.4 --- Inventory holding costs / Chapter 4.4.5 --- Quantity of capacity available for production / Chapter 4.4.6 --- Capacity absorption rate / Chapter 4.4.7 --- Generation of larger problems / Chapter 4.4.8 --- Initialization of Lagrangean multipliers / Chapter 4.4.9 --- Selection of the extent of geometrical reduction and exponential smoothing / Chapter 4.4.10 --- Close test / Chapter 4.5 --- Open test --- p.92 / Chapter 4.6 --- Managerial Implications --- p.95 / Chapter 4.7 --- Comparison with other approaches --- p.96 / Chapter 4.7.1 --- Gilbert and Madan's approach / Chapter 4.7.2 --- Our algorithm for CLS problem with setup time consideration / Chapter 4.8 --- Summary --- p.102 / Chapter Chapter 5 --- Conclusion --- p.104 / Appendix A Vogel's approximation method --- p.106 / Bibliography --- p.107

Due to the inherent complexity of the power-controlled scheduling problem, finding optimal schedules and power allocations for large-size networks will still consume extraordinary large amounts of time despite the performance of our method. We therefore propose an approximation algorithm, called the Guaranteed and Greedy Scheduling (GGS), which can find near optimal solutions within a short runtime. GGS is a polynomial time algorithm with a provable upper bound for the approximation ratio relative to the optimal solution. / For the distributed scheduling algorithm design, we focus on the CSMA (Carrier-Sense Multiple-Access) network, which is the most widely used distributed wireless network in practice. We establish a rigorous conceptual framework, upon which effective solutions to interference-safe transmissions can be constructed under the physical interference model. Specifically, we propose to use the concept of "safe carrier sensing range", which guarantees interference-safe transmissions under the physical interference model. We further propose a novel carrier-sensing mechanism, called Incremental-Power Carrier-Sensing (IPCS), which implements the safe carrier-sensing range concept in a simple way. Extensive simulation results show that IPCS can boost spatial reuse and network throughput by more than 60% relative to the conventional carrier-sensing mechanism. / This thesis studies the wireless link scheduling problem under the physical interference model. Such problem is more realistic than the widely studied wireless scheduling problem under the protocol interference model. However, it is a challenging problem because the physical interference model considers the cumulative effect of the interference powers from all the other concurrent transmitters. This thesis covers the complexity analysis and algorithm design (both centralized and distributed) for such a challenging problem. / We first give a rigorous NP-completeness proof for the power-controlled scheduling with consecutive transmission constraint under the physical interference model. We then present a centralized scheduling algorithm based on a column generation method which finds the optimal schedules and transmit powers. We further consider an integer constraint that requires the number of time slots allocated to a link to be an integer. Building upon the column generation method, we propose a branch-and-price method which can find the optimal integer solution. By simplifying the pricing problem and designing a new branching rule, we significantly improve the efficiency of both the column generation and the branch-and-price methods. For example, the average runtime is reduced by 99.86% in 18-link networks compared with the traditional column generation method. / Fu, Liqun. / Advisers: Soung Chang Liew; Jianwei Huang. / Source: Dissertation Abstracts International, Volume: 73-03, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 133-144). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

published_or_final_version / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

In recent years, lots of research effort was spent on the integration of process planning and job-shop scheduling. Various integrated process planning and scheduling (IPPS) models and solution approaches have been proposed. The previous and existing research approaches are able to demonstrate the feasibility of implementing IPPS. However, most of them assumed that setup time is negligible or only part of the processing time. For machined parts, the setup for each operation includes workpiece loading and unloading, tool change, etc. For setup that depends only on the operation to be processed (sequence-independent), it is applicable to adopt the assumption of not considering setup in IPPS. For setup that depends on both the operation to be processed and the immediately preceding operation (sequence-dependent), it is an oversimplification to adopt such assumption. In such cases, the setup time varies with the sequence of the operations. The process plans and schedules constructed under such assumption are not realistic or not even feasible. In actual practice, therefore, the setup time should be separated from the process time in performing the IPPS functions. In this thesis, a new approach is proposed for IPPS problems with setup time consideration for machined parts. Inseparable and sequence-dependent setup requirements are added into the IPPS problems. The setup times are separated from the process times and they vary with the sequence of the operations. IPPS is regarded as NP-hard problem. With the separated consideration of setup times, it becomes even more complicated. An Ant Colony Optimization (ACO) approach is proposed to handle this complicated problem. The system is constructed under a multi-agent system (MAS). AND/OR graph is used to record the set of feasible production procedures and sequences. The ACO algorithm computes results by an autocatalytic process with the objective to minimize the makespan. Software agents called “artificial ants” traverse through the feasible routes in the graph and finally construct a schedule. A setup time parameter is added into the algorithm to influence the ants to select the process with less setup time. The approach is able to construct a feasible solution with less setup time. Experimental studies have been performed to evaluate the performance of MAS-ACO approach in solving IPPS problems with separated consideration of setup times. The experimental results show that the MAS-ACO approach can effectively handle the problem. / published_or_final_version / Industrial and Manufacturing Systems Engineering / Master / Master of Philosophy

Not available / text

published_or_final_version / Mathematics / Master / Master of Philosophy

No description available.

No description available.

No description available.

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2007. / Committee Chair: Al-Khayyal, Faiz; Committee Member: Barnes, Earl; Committee Member: Johnson, Ellis; Committee Member: Karimi, IA; Committee Member: Sokol, Joel.