by Wong Tin-Lam. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references (leaves 70-73). / Abstract --- p.ii / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Scheduling Problems --- p.1 / Chapter 1.2 --- Literature Review --- p.4 / Chapter 1.2.1 --- Sized Multiprocessor Task Scheduling --- p.5 / Chapter 1.2.2 --- Fixed Multiprocessor Task Scheduling --- p.6 / Chapter 1.2.3 --- Set Multiprocessor Task Scheduling --- p.8 / Chapter 1.3 --- Organization of Thesis --- p.10 / Chapter 2 --- Overview --- p.11 / Chapter 2.1 --- Machine Environment --- p.11 / Chapter 2.2 --- The Jobs and Their Requirements --- p.12 / Chapter 2.3 --- Assumptions --- p.13 / Chapter 2.4 --- Constraints --- p.14 / Chapter 2.5 --- Objective --- p.15 / Chapter 2.6 --- An Illustrative Example --- p.17 / Chapter 2.7 --- NP-Hardness --- p.20 / Chapter 3 --- Methodology --- p.22 / Chapter 3.1 --- Dynamic Programming --- p.22 / Chapter 3.1.1 --- Problem Analysis --- p.24 / Chapter 3.2 --- Key Idea to solve the problem --- p.27 / Chapter 3.3 --- Algorithm --- p.28 / Chapter 3.3.1 --- Phase 1 --- p.28 / Chapter 3.3.2 --- Phase 2 --- p.37 / Chapter 4 --- Extensions --- p.46 / Chapter 4.1 --- "Polynomially Solvable Cases P2 --- p.46 / Chapter 4.1.1 --- Dynamic Programming --- p.47 / Chapter 4.2 --- "Set Problem P2/setj,prmp/TmaX" --- p.55 / Chapter 4.2.1 --- Processing times for set jobs --- p.56 / Chapter 4.2.2 --- Algorithm --- p.58 / Chapter 4.3 --- k´ؤMachine Problem with only two types of jobs --- p.64 / Chapter 5 --- Conclusion and Future Work --- p.67 / Chapter 5.1 --- Conclusion --- p.67 / Chapter 5.2 --- Some Future Work --- p.68 / Bibliography --- p.70

Thesis (B.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Bibliography: leaf 54. / by Paul Alan Roush. / B.S.

Process planning and scheduling are two important manufacturing planning functions which are closely related to each other. Usually, process planning and scheduling have to be performed sequentially, whereby the process plans are the input for scheduling. Many investigations have shown that the separate conduction of the two functions is much likely to ruin the effectiveness and feasibility of the process plans and schedules, and it is also difficult to cater for the occurrence of uncertainties in the dynamic manufacturing environment. The purpose of integrated process planning and scheduling (IPPS) is to perform the two functions concurrently. IPPS is a typical combinatorial optimization problem which belongs to the category of NP-hard problems. Research on IPPS has intensified in recent years. Researchers have reported various IPPS systems and solution approaches which are able to generate good solutions for specific IPPS problems. However, there is in general an absence of theoretical models for the IPPS problem representation, and research on the theoretical aspects of the IPPS is limited. The objective of this research is to establish a metaheuristic-based solution approach for the IPPS problem in flexible jobshop type of manufacturing systems. To begin with, a graph-based modeling approach for formulating the IPPS problem domain is proposed. This approach defines a way to use a category of AND/OR graphs to construct IPPS models. The graph-based IPPS model can be formulated using mathematical programming tools including polynomial mixed integer programming (PMIP) and mixed integer linear programming (MILP). The analytical mathematical programming approaches can be used to solve simple IPPS instances but they are not capable for large-scale IPPS problems. This research proposes a new IPPS modelling approach to incorporate metaheuristics in the solution strategy. Actually, the solution strategy comprises the metaheuristics and a mapping function. The metaheuristic is responsible for generating the operation sequences; a mapping function is then used to assign the operations to appropriate time slots on a schedule. General studies of applying constructive and improvement metaheuristics to solve the IPPS problem are conducted in this research. The ant colony optimization (ACO) is applied as a representative constructive metaheuristic, and a nonstandard genetic algorithm approach object-coding genetic algorithm (OCGA) is implemented as an improvement metaheuristic. The OCGA contains dedicated genetic operations to support the object-based genetic representation, and three particular mechanisms for population evolution. The metaheuristic-based solution approaches are implemented in a multi-agent system (MAS) platform. The hybrid MAS and metaheuristics based IPPS solution methodology is able to carry out dynamic rescheduling to cope with occurrence of uncertainties in practical manufacturing environments. Experiments have been carried out to test the IPPS solution approach proposed in this thesis. It is shown that both metaheuristics, ACO and OCGA, are having good performance in terms of solution quality and computational efficiency. In particular, due to the special genetic operations and population evolutionary mechanisms, the OCGA shows great advantages in experiments on benchmark problems. Finally, it is shown that the hybrid approach of MSA and metaheuristics is able to support real-time rescheduling in dynamic manufacturing systems. / published_or_final_version / Industrial and Manufacturing Systems Engineering / Doctoral / Doctor of Philosophy

No description available.

A decision support system (DSS) for nurse scheduling in hospitals is developed and implemented on microcomputer. The system includes algorithms and databases for developing weekly work and shift patterns and combining these into working schedules for nurses for a specified time horizon, and interface modules for the user to interact with the system. The system combines heuristic modeling with decision analysis concepts to generate nurse schedules. A heuristic best-first search technique is used in implementing pattern generation and screening process to satisfy both nurses and hospital's objectives. Emphasis in the design of the DSS has been on computational efficiency and user acceptability. The system is flexible so that it can be implemented in different hospital environments, and incorporates a wide range of hospital and nurses' objectives. / Graduation date: 1992

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

Stanley B. Gershwin, Ramakrishna Akella, and Yong Choong. / Bibliography: p. 36. / "February, 1984." / Contract DAAK11-82-K-0018.

The objective of this research project was to identify the limitations associated with schedule-based Material Requirements Planning (SBMRP) and to present a knowledge-based expert system (KBES) approach to solve these problems. In SBMRP, the basic strategy is to use backward or forward scheduling based on an arbitrary dispatching rule, such as First-In First-Out. One of the SBMRP weak points is that it does not use such job information as slack times, due dates, and processing times, information which otherwise is important to good scheduling decisions. In addition, the backward scheduling method produces a better schedule than the forward scheduling method in terms of holding and late costs. Dependent upon job characteristics, this may or may not be true and should be tested. This study focused on the means to overcome these two weak points by the use of a KBES. Heuristic rules were developed through an experiment-based knowledge acquisition process to generate better schedules, rather than relying solely upon forward or backward scheduling. Scheduling performance was measured, based on the minimization of the sums of holding and late costs. Due to complexities of the problem, heuristic methods were used rather than analytic methods. In particular, five loading rules were selected, based upon their close relationship to selected job characteristics, including processing times and due dates. Combined loading methods (CLMs) were developed to obtain better performance, derived by combining the two existing SBMRP scheduling strategies with five loading heuristic rules. This resulted in the generation of 10 CLMs for further evaluation. Since this study proposed a new approach, an expert human scheduler was not available. To overcome this problem, knowledge acqusition through computer experimentation (KACE) was utilized, based upon an architecture of five components: job generator, scheduler, evaluator, rule generator (an extended version of ID3), and the KBES. The first three components were used to generate a large number of examples required by the rule generator to derive knowledge. This derived knowledge was incorporated into the KBES. Experimental results indicated that the KBES outperformed the two existing SBMRP methods. Based on sensitivity analysis, the KBES exhibited robust performance with regard to every job parameter except number of parts. As the number of parts was increased, KBES performance was subject to degradation since the possibility of interactions or conflicts between parts tended to increase, resulting in shifting the threshold ratio of total available time to total processing time. Thus, it is strongly recommended that a new KBES capable of accommodating 30 parts or more should be developed using the KACE method. / Graduation date: 1991

published_or_final_version / Civil Engineering / Doctoral / Doctor of Philosophy

No description available.