no / No / Scheduling systems based on traditional heuristic rules, which deal with the complexities of manufacturing systems, have been used by researchers for the past six decades. These heuristics rules prioritise all jobs that are waiting to be processed on a resource. In this paper, a novel Index Based Heuristic (IBH) solution for the Job Shop Scheduling Problem (JSSP) is presented with the objective of minimising the overall Makespan (Cmax). The JSSP is still a challenge to researchers and is far from being completely solved due to its combinatorial nature. JSSP suits the challenges of current manufacturing environments. The proposed IBH calculates the indices of candidate jobs and assigns the job with the lower index value to the available machine. To minimise the gap between jobs, a swap technique is introduced. The swap technique takes candidate jobs for a machine and swaps them without violating the precedence constraint. Several benchmark problems are solved from the literature to test the validity and effectiveness of the proposed heuristic. The results show that the proposed IBH based algorithm outperforms the traditional heuristics and is a valid methodology for JSSP optimization.

In this paper we study a complex real world workforce scheduling problem. We apply constructive search and variable neighbourhood search (VNS) metaheuristics and enhance these methods by using a variable fitness function. The variable fitness function (VFF) uses an evolutionary approach to evolve weights for each of the (multiple) objectives. The variable fitness function can potentially enhance any search based optimisation heuristic where multiple objectives can be defined through evolutionary changes in the search direction. We show that the VFF significantly improves performance of constructive and VNS approaches on training problems, and "learn" problem features which enhance the performance on unseen test problem instances.

Classical planning problems consist of an environment in a predefined state; a set of deterministic actions that, under certain conditions, change the state of the environment; and a set of goal conditions. A solution to a classical planning problem is a sequence of actions that leads from the initial state to a state satisfying the problem’s goal conditions. There are many methods for finding solutions to classical planning problems, and a popular technique is to exploit structures that commonly occur. One such structure, apparent in many planning domains, is a breakdown of the problem into multiple agents. However, methods for finding and exploiting multiagent structures are not prevalent in the literature and are currently not competitive. This thesis sets out to rectify this problem. Its first main contribution, is to introduce a domain independent algorithm for extracting multiagent structure from classical planning problems. The algorithm relies on identifying a generalisable property of agents in planning; namely, that agents are entities with an internal state, a part of the planning problem that, under a certain distribution of actions, only they can modify. Once this is appropriately formalised, the decomposition algorithm is introduced and is shown to produce identifiably multiagent decompositions over all of the classical planning domains used in the International Planning Competitions, even finding more detailed decompositions than are used by humans in certain cases. Solving multiagent planning problems can be challenging because a solution may require complex inter-agent coordination. The second main contribution of the thesis is a heuristic planning algorithm that effectively exploits the structure of decomposed domains. The algorithm transforms the coordination problem into a process of subgoal generation that can be solved efficiently under a well-known relaxation in planning. The generated subgoals guide the search so that it is always performed by one single-agent subproblem at a time. The algorithm is evaluated and shown to greatly outperform current state-of-the-art planners over decomposable domains. The thesis also includes discussion of the possible extensions of this work, to include the multiagent concepts of self-interested agents and concurrent actions. Results from the multiagent planning literature are improved upon and a new solution concept is presented that accounts for the ‘farsightedness’ inherent in planning. A method is then presented that can find stable solutions for a certain class of multiagent planning problems. A new method is introduced for modelling concurrent actions that allows them to be written without requiring knowledge of each other agent in the domain, and it is shown how such problems can be solved by a translation to single-agent planning.

published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

by Siu Wai-man, Raymond. / Bibliography: leaves 75-76 / Thesis (M.B.A.)--Chinese University of Hong Kong, 1986

Through the composition of ten pieces, I have explored the theme of mimesis and musical pluralism, especially as it occurs and applies in my own music. The following commentary begins by initially discussing my own context as a composer, providing an overview of the motivations that first prompted me to investigate and research this topic. After this background is explained, I examine key philosophical concepts connected to both mimesis and artistic pluralism, with the latter being chiefly concerned with how it affects the creation of new musical works. With the above issues having been discussed, this context effectively frames the next seven chapters of this commentary, which involves analysis and examination of ten works I composed for this doctoral degree. This begins with a thorough analysis of two chamber works and then moves onto an in-depth elaboration about a more expansive ensemble work of forty-minutes. After this discussion, I present a series of mimetically related works; compositions more theoretical in design and concept, yet still illustrating and building upon the central theme of this artistic research. Lastly, three other works are examined, demonstrating similar and contrasting compositional approaches. The concluding chapter of the commentary presents a succinct but thorough overview of the ramifications of the above compositions - focusing primarily on the relative success of these works, as well as their shortcomings, potential for future exploration, possible refinement, and overall connection to the theme of mimesis and musical pluralism.

So Wai Kuen. / Year shown on spine: 1997. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1996. / Includes bibliographical references (leaves 87-92). / INTRODUCTION --- p.1 / Chapter 1.1 --- Introduction to SLCR Problem --- p.1 / Chapter 1.2 --- Our Contributions --- p.1 / Chapter 1.3 --- Organization of the thesis --- p.3 / LITERATURE REVIEW --- p.4 / Chapter 2.1 --- Research in the Capacitated Resource Constraint Problem --- p.4 / Chapter 2.2 --- The Single Level Constrained Resource Problem --- p.5 / Chapter 2.3 --- The Multiple Level Constrained Resource Problem --- p.8 / Chapter 2.4 --- Research in the Fixed Charge Problem --- p.9 / Chapter 2.4.1 --- Approximate Methods --- p.9 / Chapter 2.4.2 --- Exact Methods --- p.10 / Chapter 2.5 --- Conclusion --- p.11 / THE SLCR PROBLEM WITH BACKORDERING --- p.12 / Chapter 3.1 --- Problem Description and Formulation --- p.13 / Chapter 3.2 --- Description of the heuristic --- p.19 / Chapter 3.2.1 --- Phase I --- p.19 / Chapter 3.2.2 --- Phase II --- p.26 / Chapter 3.3 --- Design of Computational Experiments --- p.30 / Chapter 3.3.1 --- Specifications of test problems ( 3 products and 12 period case ) --- p.31 / Chapter 3.3.2 --- Computation of the Lower Bound --- p.38 / Chapter 3.4 --- Computational Results --- p.39 / Chapter 3.5 --- Comparison to Millar and Yang's Algorithm --- p.48 / Chapter 3.5.1 --- Comparison Results --- p.49 / Chapter 3.6 --- Conclusion --- p.50 / THE OPTIMIZATION BASED ALGORITHM --- p.51 / Chapter 4.1 --- The Formulation --- p.52 / Chapter 4.2 --- The Algorithm --- p.60 / Chapter 4.2.1 --- Phase I --- p.60 / Chapter 4.2.2 --- Phase II --- p.63 / Chapter 4.2.3 --- Phase III --- p.70 / Chapter 4.3 --- An Illustrative Example --- p.72 / Chapter 4.4 --- Computational Results --- p.79 / Chapter 4.5 --- Conclusion --- p.84 / CONCLUSION --- p.85 / BIBLIOGRAPHY --- p.87

The facility layout design problem is concerned with determining the arrangement and configuration of facilities, which optimizes a prescribed objective such as profit, cost, or distance, and which satisfies various prescribed constraints pertaining to available resources. In industry, facility layout design problems arise in manufacturing, in warehousing, and in various assignment type situations. The solution of these problems impacts on the viability of the industry. For example, material-handling costs which can comprise between 30 and 75% of the total manufacturing costs, can be reduced by using the optimization methods associated with the facility layout design. In the service industries, facility layout design problems arise in the location of emergency facilities (such as ambulance, fire stations) and in the allocation of space. The solution of these location problems impacts on the well being of the community. Mathematically, the facility layout problem has been modelled as: a quadratic assignment problem, a quadratic set covering problem, a linear integer programming problem, a mixed integer programming problem, and a graph theoretic problem. The problem has been shown to be NP-complete. This computational difficulty has led researchers to consider suboptimal solutions generated by heuristic approaches. There are a number of heuristic procedures that have been proposed for solving the facility layout design problem, including Simulated Annealing, Tabu Search, Expert Systems, and Graph Theoretic Algorithms. The most successful heuristic approaches are based on graph theoretic concepts. In this thesis we focus our study on constructive graph theoretic based heuristics for determining an optimal arrangement and configuration of facilities with the objective of maximizing the total benefit. / We are particularly interested in constructive heuristics, which can produce a maximum-weighted planar graph as a final solution. Our contribution is the development, implementation, and testing of three new algorithms. Computational results, based on 4200 randomly (uniform and normal distribution) generated problems, demonstrate the value of our methods. We also present the performance of each algorithm when various initial solutions are applied. Chapter 1 provides the background of the facility layout design, including the notation, terminology and general concepts as well as a summary of the thesis. Chapter 2 provides a comprehensive survey of the facility layout design problem. This includes models and methods of solution based on exact algorithms (including the branch and bound method and the cutting plane method), as well as heuristic algorithms. We detail the main constructive graph theoretic based heuristics in the literature: the Deltahedron Method, the Green-Al Hakim Algorithm, the Leung’s Constructive Heuristic, the Kim-Kim Algorithm, the Wheel Expansion Method, TESSA and the String Processing Algorithm. We also briefly discuss the non-graph theoretic heuristics including simulated annealing, tabu search, and expert systems. In Chapter 3 we present three new graph theoretic based heuristics. These heuristics are constructive and the solution is built up, starting with an initial layout of four facilities, by an insertion process. Our algorithms have two important features. Firstly, they allow for previously chosen edges to be removed at each insertion step. Secondly, they do not restrict the type of maximal planar graph produced. Computational results and a comparative analysis of the main graph theoretic based heuristics are provided. The analysis is based on 4200 randomly generated test problems (from uniform and normal distribution). / The test problems consist of 30 data sets with the number of facilities ranging from 5 to 100 in increments of 5. Chapter 4 is devoted to the performance of graph theoretic based heuristics when different types of initial solutions are applied. Examples show that the final solution is sensitive to the initial solution. Computational results indicate that for most algorithms, the best type of initial solution is the selection of four facilities which yield the best objective function value contribution. However, this does not always coincide with that proposed in the original description of the algorithms. We conclude this thesis by discussing some future research that can be carried out on the facility layout design problem, particularly in graph theoretic based heuristics.

Two methods of obtaining approximate solutions to the classic General Job-shop Scheduling Program are investigated. The first method is iterative. A sampling of the solution space is used to decide which of a collection of space pruning constraints are consistent with "good" schedules. The selected space pruning constraints are then used to reduce the search space and the sampling is repeated. This approach can be used either to verify whether some set of space pruning constraints can prune with discrimination or to generate solutions directly. Schedules can be represented as trajectories through a Cartesian space. Under the objective criteria of Minimum maximum Lateness family of "good" schedules (trajectories) are geometric neighbors (reside with some "tube") in this space. This second method of generating solutions takes advantage of this adjacency by pruning the space from the outside in thus converging gradually upon this "tube." One the average this methods significantly outperforms an array of the Priority Dispatch rules when the object criteria is that of Minimum Maximum Lateness. It also compares favorably with a recent relaxation procedure.

In this thesis, we study theoretically and empirically the additive abstraction-based heuristics. First we present formal general definitions for abstractions that extend to general additive abstractions. We show that the general definition makes proofs of admissibility, consistency, and additivity easier, by proving that several previous methods for defining abstractions and additivity satisfy three imple conditions. Then we investigate two general methods for defining additive abstractions and run experiments to determine the effectiveness of these methods for two benchmark state spaces: TopSpin and the Pancake puzzle. Third, we propose that the accuracy of the heuristics generated by abstraction can be improved by checking for infeasibility. The theory and experiments demonstrate the approach to detect infeasibility and the application of this technique to different domains. Finally, we explore the applications of additive abstraction-based heuristics in two state spaces with nonuniform edge costs: the Sequential Ordering Problem (SOP) and the weighted Pancake puzzle. We formalize a novel way of generating additive and non-additive heuristics for these state spaces. Furthermore, we investigate the key concepts to generate good additive and non-additive abstractions. Experiments show that compared to some simple alternative heuristics, well chosen abstractions can enhance the quality of suboptimal solutions for large SOP instances and reduce search time for the weighted Pancake problems.