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.

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.

Unrelated parallel machines are machines that perform the same function but have different capacity or capability. Thus, the processing time of each job would be different on machines of different types. The scheduling environment considered is dynamic in both job release time and machine availability. Additionally, each job considered can have different weight, and due date. Split jobs are also considered in this research. The number of jobs that needs to be processed in split-modes is pre-determined and not part of the scheduling decision. Additional constraints are imposed on split jobs to ensure that the absolute difference in completion time of the split portions of a job is within a user-specified margin. These constraints are supported by the Just-In-Time manufacturing concept where inventory has to be maintained at a very low or zero level. The objective of this research is to minimize the sum of the weighted tardiness of all jobs released within the planning horizon. The research problem is modeled as a mixed (binary) integer-linear programming model and it belongs to the class of NP-hard problems. Thus, one cannot rely on using an implicit enumeration technique, such as the one based on branch-and-bound, to solve industry-size problems within a reasonable computation time. Therefore, a higher-level search heuristic, based on a concept known as tabu search, is developed to solve the problems. Four different methods based on simple and composite dispatching rules are used to generate the initial solution that is used by tabu-search as a starting point. Six different tabu-search based heuristics are developed by incorporating the different features of tabu search. The heuristics are tested on eight small problems and the quality of their solutions is compared to their optimal solutions, which are obtained by applying the branch-and-bound technique. The evaluation shows that the tabu-search based heuristics are capable of obtaining solutions of good quality within a much shorter time. The best performer among these heuristics recorded a percentage deviation of only 1.18%. The performance of the tabu-search based heuristics is compared by conducting a statistical experiment that is based on a split-plot design. Three sizes of problem structures, ranging from 9 jobs to 60 jobs and from 3 machines to 15 machines are used in the experiment. The results of the experiment reveal that in comparison to other initial-generation methods, the composite dispatching rule is capable of obtaining initial solutions that significantly accelerate the tabu search based heuristic to get to the final solution. The use of long-term memory function is proven to be advantageous in solving all problem structures. The long-term memory based on maximum-frequency strategy is recommended for solving the small problem structure, while the minimum-frequency strategy is preferred for solving medium and large problem structures. With respect to the use of tabu-list size as a parameter, the variable tabu-list size is preferred for solving the smaller problem structure, but the fixed tabu-list size is preferred as the size of the problems grows from small to medium and then large. / Graduation date: 2000

Thesis (M.S.)--Rochester Institute of Technology, 2007. / Typescript. Includes bibliographical references (leaves 86-90).

Thesis (Ph. D.)--Lehigh University, 2000. / Includes vita. Includes bibliographical references (leaves 125-135).

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