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

The research presented in this dissertation addresses the Multi-Mode Resource-Constrained Project Scheduling Problem (MMRCPSP) in the presence of resource unavailability. This research is motivated by the scheduling of engineering design tasks in automotive product development to minimize the project completion time, but addresses a general scheduling situation that is applicable in many contexts. The current body of MMRCPSP research typically assumes that, 1) individual resource units are available at all times when assigning tasks to resources and, 2) before assigning tasks to resources, there must be enough resource availability over time to complete the task without interruption. In many situations such as assigning engineering design tasks to designers, resources are not available over the entire project-planning horizon. In the case of engineering designers and other human resources, unavailability may be due to several reasons such as vacation, training, or being scheduled to do other tasks outside the project. In addition, when tasks are scheduled they are often split to accommodate unavailable resources and are not completed in one continuous time segment. The objectives of this research are to obtain insight into the types of project scheduling situations where task splitting may result in significant makespan improvements, and to develop a fast and effective scheduling heuristic for such situations. A designed computational experiment was used to gain insight into when task splitting may provide significant makespan improvements. Problem instances were randomly generated using a modification of a standard problem generator, and optimally solved with and without task splitting using a branch and bound algorithm. In total 3,880 problem instances were solved with and without task splitting. Statistical analysis of the experimental data reveals that high resource utilization is the most important factor affecting the improvements obtained by task splitting. The analysis also shows that splitting is more helpful when resource unavailability occurs in multiple periods of short duration versus fewer periods of long duration. Another conclusion from the analysis indicates that the project precedence structure and the number (not amount) of resources used by tasks do not significantly affect the improvements due to task splitting. Using the insights from the computational testing, a new heuristic is developed that can be applied to large problems. The heuristic is an implementation of a simple priority rule-based heuristic with a new parameter used to control the number of task splits. It is desirable to obtain the majority of task splitting benefits with the smallest number of split tasks. Computational experiments are conducted to evaluate its performance against known optimal solutions for small sized problems. A deterministic version of the heuristic found optimal solutions for 33% of the problems and a stochastic version found optimal solutions for over 70%. The average percent increase in makespan compared to optimal was 7.58% for the deterministic heuristic and less than 2% for the stochastic versions demonstrating acceptable performance. / Graduation date: 2003

This thesis is intended to provide the management of small to medium sized job shop companies with a written plan to implement a formal computerized manufacturing planning and control system. The research stemmed from a case study performed at a typical job shop where growth of production activities was complicating the informal control system being used. A review of the literature and a survey of job shops provided the necessary foundation for this implementation. Research indicated that typical material requirements planning (MRP) systems do not provide the type of shop floor control that most job shops require. This thesis suggests alternatives that not only provide the type of shop floor control required by a typical job shop, but software that can be managed effectively by current employees with minimal changes to the education and training of these employees. The plan contains ten steps that are designed to be used by a job shop wishing to implement a formal computerized control system. A decision making heuristic is used in the first step that provides a method for estimating the benefits that might result from implementation. Sample criteria for evaluating current shop floor control software, development of an implementation timeline, cost considerations, educational requirements for employees, and suggested methods for measuring project performance are also included. Examples of the type of improvement that can be expected for each of the business activities is also discussed. The overall goal is to provide a comprehensive plan that will guide managers through the steps necessary to implement a computerized shop floor control system and to inform managers of the benefits which can accrue from such a system. / Graduation date: 1999

This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the “Preflow Push” algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.

This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the “Preflow Push” algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.

Production scheduling is a common problem that occurs in multi-product manufacturing facilities where a wide range of products are produced in small quantities, resulting in frequent changeovers. A plastics compounding plant offering tailor-made resins is a representative case. This kind of scheduling problem has already been extensively researched and published in the past. However, the concept of incorporating quality of the finished product has never been visited previously. There are many different factors that may affect the quality of polymer resins produced by extrusion. One such factor is temperature. A production schedule cannot be related to the temperature or quality in any direct manner, and any other indirect relationships are not very apparent. The key to a correlation between the temperature of the processed material and the production schedule is the extruder flow rate. The flow rate affects the temperature of the molten plastic inside the extruder barrel, which means it also directly affects the quality of the final resin. Furthermore, the extruder is the critical machine in the extrusion process. Therefore, it determines the processing time of an order, serving as the basis for the scheduling problem. The extruded polymer resin must undergo quality control testing to ensure that quantitative quality measurements must meet specifications. This is formulated as a constraint, where the extruder flow rate is determined to generate an optimized production schedule while ensuring the quality is within range. The general scheduling problem at a plastics compounding plant is formulated as a mixed integer linear programming (MILP) model for a semi-continuous, multi-product plant with parallel production lines. The incorporation of quality considerations renders the problem a mixed integer nonlinear program (MINLP). Another objective of the proposed research deals with providing insight into the economic aspects of the scheduling process under consideration. The scheduling problem is analyzed and relations for its various cost components are developed. A total opportunity cost function was suggested for use as the comprehensive criterion of optimality in scheduling problems. Sensitivity analysis showed that none of the individual criteria gives optimal or near optimal results when compared to the total opportunity cost.

Production scheduling is a common problem that occurs in multi-product manufacturing facilities where a wide range of products are produced in small quantities, resulting in frequent changeovers. A plastics compounding plant offering tailor-made resins is a representative case. This kind of scheduling problem has already been extensively researched and published in the past. However, the concept of incorporating quality of the finished product has never been visited previously. There are many different factors that may affect the quality of polymer resins produced by extrusion. One such factor is temperature. A production schedule cannot be related to the temperature or quality in any direct manner, and any other indirect relationships are not very apparent. The key to a correlation between the temperature of the processed material and the production schedule is the extruder flow rate. The flow rate affects the temperature of the molten plastic inside the extruder barrel, which means it also directly affects the quality of the final resin. Furthermore, the extruder is the critical machine in the extrusion process. Therefore, it determines the processing time of an order, serving as the basis for the scheduling problem. The extruded polymer resin must undergo quality control testing to ensure that quantitative quality measurements must meet specifications. This is formulated as a constraint, where the extruder flow rate is determined to generate an optimized production schedule while ensuring the quality is within range. The general scheduling problem at a plastics compounding plant is formulated as a mixed integer linear programming (MILP) model for a semi-continuous, multi-product plant with parallel production lines. The incorporation of quality considerations renders the problem a mixed integer nonlinear program (MINLP). Another objective of the proposed research deals with providing insight into the economic aspects of the scheduling process under consideration. The scheduling problem is analyzed and relations for its various cost components are developed. A total opportunity cost function was suggested for use as the comprehensive criterion of optimality in scheduling problems. Sensitivity analysis showed that none of the individual criteria gives optimal or near optimal results when compared to the total opportunity cost.

Thesis (Ph. D.)--University of Texas at Austin, 1999. / Vita. Includes bibliographical references (leaves 125-135). Available also in a digital version from Dissertation Abstracts.

Includes bibliographical references (p. 46-48).

Thesis (M. Phil.)--University of Hong Kong, 1988.