No description available.

No description available.

Production scheduling is a notoriously difficult problem. Manufacturing environments contain complex, time-critical processes, which create highly constrained scheduling problems. Genetic algorithms (GAs) are optimisation tools based on the principles of evolution. They can tackle problems that are mathematically complex, or even impossible to solve by traditional methods. They allow problem-specific implementation, so that the user can develop a technique that suits the situation, whilst still providing satisfactory schedule optimisation performance. This work tests GA optimisation on a real-life scheduling application, a chilled ready-meal factory. A schedule optimisation system is required to adapt to changing problem circumstances and to include uncertain or incomplete information. A GA was designed to allow successive improvements to its effectiveness at scheduling. Three objectives were chosen for minimisation. The GA proved capable of finding a solution that attempted to minimise the sum of the three costs. The GA performance was improved after experiments showed the effects of rules and preference modelling upon the optimisation process, allowing 'uncertain' data to be included. Multi-objective GAs (MOGAs) minimise each cost as a separate objective, rather than as part of a single-objective sum. Combining Pareto-optimality with varying emphasis on the conflicting objectives, a set of possible solutions can be found from one run of MOGA. Each MOGA solution represents a different situation within the factory, thus being well suited to a constantly changing manufacturing problem. Three MOGA implementations are applied to the problem; a standard weighted sum, two versions of a Pareto-optimal method and a parallel populations method. Techniques are developed to allow suitable comparison of MOGAs. Performance comparisons indicate which method is most effective for meeting the factory's requirements. Graphical and statistical methods indicate that the Pareto-based MOGA is most effective for this problem. The MOGA is demonstrated as being a highly applicable technique for production schedule optimisation.

Approved for public release; distribution is unlimited / Each year the United States Marine Corps suffers excessive loss of man years from Marines awaiting entry-level schools. During fiscal year 2001 (the most recent complete time-awaiting-training data), Marines exceeded 2,800 man years of time awaiting training. Non-infantry personnel comprise 80% of the more than 30,000 recruits shipped to Marine Corps Recruit Depots each year, but they constitute almost 95% of the 2,800 man-year loss. Marine Corps manpower planners consider the current level of loss unacceptable and believe significant improvement can be gained by optimally scheduling courses at Military Occupational Specialty (MOS) schools. This thesis uses an integer linear program, Entry-Level Course Scheduler (ELCS), to optimize a course schedule that includes recommended seat assignments by MOS and gender. ELCS seeks to minimize the time awaiting training while successfully meeting yearly classification requirements. ELCS results using fiscal year 2003 data indicate time awaiting training can be reduced to only 1,700 man years (a 1,100 man-year improvement, when compared with fiscal year 2001 data). / Captain, United States Marine Corps

No description available.

Thesis (Ph.D.)--Boston University / PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you. / A multimedia system combines audio, video, graphics, and text into one presentation. Each of these multimedia data types has distinct temporal characteristics. For example video has a specific number of frames that must be displayed per second. There are also temporal relationships that exist between the media. In a movie application, the audio and video streams must be synchronized to achieve a lip syncing effect. In our system, we manage these temporal requirements through the scheduling of the communication channel; multimedia data is retrieved across the network at the appropriate time so that temporal presentation requirements are met. This real-time scheduling forms a basis for the limited a priori (LAP) scheduler. The scheduler assumes that it knows enough about the system a priori to schedule the next period or limited portion of the presentation. By considering only one period at a time, the scheduler can adapt to dynamic user input or changing communication channel characteristics. A network delay model and retrieval delay estimation are used by the LAP scheduler when scheduling objects so that they arrive before their playout deadlines. This modeling and estimation also allow the LAP scheduler to decide when there are changes in the communication channel performance that require adjustments to the retrieval schedule. Furthermore, they enable the LAP scheduler to lower the resource requirements of a multimedia presentation when there is less than sufficient network bandwidth or buffer space for normal playout. The characteristics of the LAP scheduler are first described by analyzing the delay estimation techniques. Properties of the LAP scheduler are further investigated by using performance results from an FDDI network simulation and from an implementation of the LAP scheduler between two Unix workstations interconnected by an Ethernet network. The LAP scheduler wss found to satisfy the proposed objectives for multimedia data retrieval. However, its performance is hindered by the difficulty in predicting network traffic patterns, the normal approximations in the estimation process, and the lack of scheduling for resources other than the communication channel. / 2031-01-01

On-demand air transportation is a recent trend in the airline industry. It allows the customer to call in days or even hours before to book a ight. Therefore, the scheduling and planning of this type of airline needs to be done daily. Hence, a successful on-demand air transportation requires an e cient ight scheduling system to construct the optimal daily ight schedules. An on-demand air transportation ight scheduling problem that arose in a Southern African industry has been studied. A new solution methodology is proposed. A number of new heuristics are used to combine ight legs for a robust solution. A time-space multi-commodity network is introduced to derive the mathematical model which is then solved using CPLEX. The results obtained are then compared with known results showing much more e cient performances and saving for the industry.

Ng Chi To. / Thesis (Ph.D.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 169-173). / Acknowledgements --- p.i / Abstract --- p.ii / Chapter Chapter 1 --- INTRODUCTION --- p.1 / Chapter 1.1 --- Problem Formulation and Motivation --- p.1 / Chapter 1.2 --- Past Research Works --- p.3 / Chapter 1.3 --- Results of the Study --- p.5 / Chapter 1.4 --- Organization of the Thesis --- p.7 / Chapter Part I --- THE CTV PROBLEM --- p.9 / Chapter Chapter 2 --- A GENERALIZATION OF SCHRAGE'S CONJEC- TURE --- p.10 / Chapter 2.1 --- Schrage's Conjecture --- p.10 / Chapter 2.2 --- Generalization --- p.13 / Chapter Chapter 3 --- ASYMPTOTIC OPTIMALITY --- p.15 / Chapter 3.1 --- Optimal Sequences under a Symmetric Structure --- p.17 / Chapter 3.2 --- An Upper Bound for the Relative Error --- p.21 / Chapter 3.3 --- Asymptotical Probabilistic Analysis --- p.25 / Chapter Chapter 4 --- ADDITIONAL FINDINGS --- p.37 / Chapter Chapter 5 --- THE BEST V-SHAPED SEQUENCE --- p.46 / Chapter 5.1 --- Transformation of the CTV Problem to a Boolean Optimization Problem --- p.47 / Chapter 5.2 --- Minimization of the Expected CTV among All the V-shaped Fixed Sequences --- p.48 / Chapter Chapter 6 --- THE WORST CASE ANALYSIS --- p.65 / Chapter 6.1 --- A Lower Bound for the CTV Problem --- p.66 / Chapter 6.2 --- A Worst Case Bound --- p.71 / Chapter Part II --- EXTENSIONS --- p.75 / Chapter Chapter 7 --- A MORE GENERAL MODEL --- p.76 / Chapter 7.1 --- Some Basic Concepts --- p.76 / Chapter 7.2 --- Problem Description --- p.78 / Chapter 7.3 --- Applications and Difficulties --- p.80 / Chapter Chapter 8 --- THE ZERO STARTING PROBLEM --- p.83 / Chapter 8.1 --- Problem Transformation --- p.85 / Chapter 8.2 --- Properties --- p.88 / Chapter 8.3 --- Algorithm A and Promising Solutions --- p.93 / Chapter 8.4 --- Time Complexity of Algorithm A --- p.94 / Chapter Chapter 9 --- PROBABILISTIC ANALYSIS OF PROMISING SO- LUTIONS --- p.95 / Chapter 9.1 --- Promising Solutions under a Symmetric Structure --- p.95 / Chapter 9.2 --- An Upper Bound for the Relative Error of Promising Solutions --- p.100 / Chapter 9.3 --- Probabilistic Analysis on the Relative Error of Promising Solutions --- p.106 / Chapter Chapter 10 --- CONCLUDING REMARKS AND FUTURE RESEARCH WORK --- p.118 / Appendix A Preliminary Results for Analysis --- p.122 / Appendix B Proofs of Some Lemmas --- p.127 / Appendix C Proofs of Some Theorems --- p.149 / Appendix D Proofs of Some Properties --- p.160 / Appendix E An Alternative to Completion Time Variance --- p.167 / Bibliography --- p.169

by Cheung Chit-Cheung, Gavin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 75-77). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgment --- p.ii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation --- p.2 / Chapter 1.2 --- Problem Description --- p.5 / Chapter 1.3 --- Contributions --- p.6 / Chapter 1.4 --- Thesis Organization --- p.6 / Chapter 2 --- Problem Formulation and Solution Approaches --- p.8 / Chapter 2.1 --- Mathematical Modeling --- p.8 / Chapter 2.2 --- Transformation of Problem --- p.11 / Chapter 2.3 --- Problem Analysis --- p.12 / Chapter 2.3.1 --- Optimality Criteria --- p.13 / Chapter 2.3.2 --- Heuristic Solutions --- p.15 / Chapter 2.4 --- Literatures Review on Single-Machine Scheduling --- p.18 / Chapter 3 --- Discussion of Some Special Cases --- p.21 / Chapter 3.1 --- Two Operations --- p.22 / Chapter 3.2 --- Identical Distributions --- p.24 / Chapter 3.2.1 --- Error Bound of LPTF - Maximum Distribution Approach --- p.27 / Chapter 3.3 --- Large Initial Time and Special Processing Times Structure --- p.29 / Chapter 3.3.1 --- Application of SVF to Exponential Distribution --- p.34 / Chapter 3.3.2 --- Error Bound of SVF 一 Switching Processing Times Approach --- p.37 / Chapter 3.3.3 --- Extended Error Bound Analysis --- p.41 / Chapter 4 --- Heuristics to Solve the General Problems --- p.47 / Chapter 4.1 --- Level 1 - PIPF and LPTF Rules --- p.48 / Chapter 4.2 --- Level 2 - Adjacent Pair wise Interchange --- p.51 / Chapter 4.3 --- Computational Complexity --- p.53 / Chapter 5 --- Experimental Results --- p.54 / Chapter 5.1 --- Design of Experiments --- p.54 / Chapter 5.1.1 --- Design of Problem Parameters --- p.55 / Chapter 5.1.2 --- Evaluation Methods --- p.57 / Chapter 5.2 --- Results Analysis --- p.59 / Chapter 5.2.1 --- Evaluation for Problems with Small Size --- p.60 / Chapter 5.2.2 --- Evaluation for Problems with Large Size --- p.63 / Chapter 6 --- Conclusion --- p.67 / Chapter 6.1 --- Summary --- p.67 / Chapter 6.2 --- Future Extension --- p.68 / Appendix --- p.69 / Chapter A --- Crossing Point of Normal Density Functions --- p.69 / Chapter B --- Probaiblity Distributions --- p.73 / Chapter B.1 --- Uniform Distribution --- p.73 / Chapter B.2 --- Exponential Distribution --- p.74 / Chapter B.3 --- Normal Distribution --- p.74 / Bibliography --- p.75

Allowing the production rate to be changed at any time, Chapter 4 investigates the optimal production and setup scheduling policy which minimizes the average inventory, backlog, and setup costs in a one-facility, two-product system. Under the optimal control, the system will reach a limit cycle in a finite time. In the cyclic schedule, each product is produced at its demand rate for a fraction of the production time. This contradicts the conventional wisdom where only one product should be produced at its demand rate. Moreover, we partially prove the optimality of the proposed policy. / Given that the unit inventory costs are nondecreasing along the route, and the last machine is the bottleneck, Chapter 2 provides an optimal production policy, which minimizes the total inventory and backlog costs in a multiple-product flow line. The production capacity is allocated to individual products according to the ranking of marginal benefits. The capacity allocation may change only when a buffer reaches the level of zero. This approach not only extends the study from the one-product system to the multiple-product system, but also has a computational complexity of O(MN), where M and N are the number of machines and the number of products in the system. In addition, it can be applied to the discounted-cost problem. The optimality of the proposed policy is further verified by the Hamilton-Jacobi-Bellman equation. / The problem of production and setup scheduling in a one-facility, multiple-product system is considered in Chapter 3. Besides the production cycle time and the lot sizes, the production rate is also a control variable. We demonstrate that the production of the product, which has the highest unit inventory and backlog costs weighted by its demand rate, should be slowed down. Our results outperform those of the classical Economic Lot Scheduling Problem. / This research significantly improves previous results of production and setup scheduling in complex, deterministic, and multiple-product systems. Insights and conditions of better production and setup scheduling are provided. These results are not only applicable to deterministic systems, but also suitable for constructing policies for stochastic systems. / This thesis is concerned with the problem of production and setup scheduling in continuous and deterministic manufacturing systems which produce multiple products with constant exogenous demands. / Jun Yang. / "October 1997." / Source: Dissertation Abstracts International, Volume: 59-11, Section: B, page: 6019. / Supervisors: Houmin Yan; Xiaoqiang Cai. / Thesis (Ph.D.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (p. 159-168). / 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 dissertations and theses, [200-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts in English and Chinese. / School code: 1307.