Operations Research, Systems Engineering and Industrial Engineering Commons^™

A Multi-Agent Approach For Solving Optimization Problems Involving Expensive Resources, Hoong Chuin Lau, H. Wang

Research Collection School Of Computing and Information Systems

In this paper, we propose a multi-agent approach for solving a class of optimization problems involving expensive resources, where monolithic local search schemes perform miserably. More specifically, we study the class of bin-packing problems. Under our proposed Fine-Grained Agent System scheme, rational agents work both collaboratively and selfishly based on local search and mimic physics-motivated systems. We apply our approach to a generalization of bin-packing - the Inventory Routing Problem with Time Windows - which is an important logistics problem, and demonstrate the efficiency and effectiveness of our approach.

Robust Temporal Constraint Networks, Hoong Chuin Lau, Thomas Ou, Melvyn Sim

Research Collection School Of Computing and Information Systems

In this paper, we propose the Robust Temporal Constraint Network (RTCN) model for simple temporal constraint networks where activity durations are bounded by random variables. The problem is to determine whether such temporal network can be executed with failure probability less than a given 0 ≤ E ≤ 1 for each possible instantiation of the random variables, and if so. how one might find a feasible schedule with each given instantiation. The advantage of our model is that one can vary the value of ∊ to control the level of conservativeness of the solution. We present a computationally tractable and …

Corrective Maintenance Optimization In An Air Force, Hoong Chuin Lau, K. Y. Neo, W. C. Wan

Research Collection School Of Computing and Information Systems

Successful military mission planning and execution depend critically on equipment serviceability and resupply. Due to the stochastic nature of demands, the forecast of optimal spares and resources needed to guarantee the level of serviceability is a complex problem, especially in a multi-echelon setting. In this paper, we propose a decision-support concept and software tool known as Corrective Maintenance Optimizer (CMO) that helps to optimize system availability, through proper allocation of spare parts, both strategically and operationally.

Job Scheduling With Unfixed Availability Constraints, Hoong Chuin Lau, C. Zhang

Research Collection School Of Computing and Information Systems

Standard scheduling theory assumes that all machines are continuously available throughout the planning horizon. In many manufacturing and service management situations however, machines need to be maintained periodically to prevent malfunctions. During the maintenance period, a machine is not available for processing jobs. Hence, a more realistic scheduling model should take into account machine maintenance activities. In this paper, we study the problem of job scheduling with unfixed availability constraints on a single machine. We first propose a preliminary classification for the scheduling problem with unfixed availability constraints based on maintenance constraints, job characteristics and objective function. We divide our …

Logistics Network Design With Differentiated Delivery Lead Time: A Chemical Industry Case Study, Michelle Lee Fong Cheong, Rohit Bhatnagar, Stephen C. Graves

Research Collection School Of Computing and Information Systems

Most logistics network design models assume exogenous customer demand that is independent of the service time or level. This paper examines the benefits of segmenting demand according to lead-time sensitivity of customers. To capture lead-time sensitivity in the network design model, we use a facility grouping method to ensure that the different demand classes are satisfied on time. In addition, we perform a series of computational experiments to develop a set of managerial insights for the network design decision making process.

Two-Echelon Repairable Item Inventory System With Limited Repair Capacity Under Nonstationary Demands, Hoong Chuin Lau, Huawei Song

Research Collection School Of Computing and Information Systems

We study a repairable item inventory system under limited repair capacity and nonstationary Poisson demands, motivated by corrective maintenance of military equipment. Our goal is to minimize the cost of both spare and repair resource allocation. We propose an efficient analytical model that combines optimization modeling and queuing theory.

A Periodic-Review Inventory Model With Application To The Continuous-Review Obsolescence Problem, Yuyue Song, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In this paper we consider a stochastic-demand periodic-review inventory model with sudden obsolescence. We characterize the structure of the optimal policy and propose a dynamic programming algorithm for computing its parameters. We then utilize this algorithm to approximate the solution to the continuous-review sudden obsolescence problem with general obsolescence distribution. We prove convergence of our approximation scheme, and demonstrate it numerically against known closed-form solutions of special cases.

A Two-Level Framework For Coalition Formation Via Optimization And Agent Negotiation, Hoong Chuin Lau, Lei Zhang

Research Collection School Of Computing and Information Systems

We present a two-level coalition formation approach based on a centralized optimization model on the upper level, and a distributed agent-negotiation model on the lower level. This approach allows us to balance agent self-interests against a high joint utility. Experimental results show that the two-level coalition formation mechanism will increase not only the overall utility of the coalition, but also the individual utility of most participating agents. The results also suggest it is better for the agents to be partially cooperative rather than either fully cooperative or self-interested in our setting.

A Development Framework For Rapid Metaheuristics Hybridization, Hoong Chuin Lau, M. K. Lim, W. C. Wan, S. Halim

Research Collection School Of Computing and Information Systems

While meta-heuristics are effective for solving large-scale combinatorial optimization problems, they result from time-consuming trial-and-error algorithm design tailored to specific problems. For this reason, a software tool for rapid prototyping of algorithms would save considerable resources. This work presents a generic software framework that reduces development time through abstract classes and software reuse, and more importantly, aids design with support of user-defined strategies and hybridization of meta-heuristics. Most interestingly, we propose a novel way of redefining hybridization with the use of the "request and response" metaphor, which form an abstract concept for hybridization. Different hybridization schemes can now be formed …

Taking Dcop To The Real World: Efficient Complete Solutions For Distributed Event Scheduling, Rajiv Maheswaran, Milind Tambe, Emma Bowring, Jonathan Pearce, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Distributed Constraint Optimization (DCOP) is an elegant formalism relevant to many areas in multiagent systems, yet complete algorithms have not been pursued for real world applications due to perceived complexity. To capably capture a rich class of complex problem domains, we introduce the Distributed Multi-Event Scheduling (DiMES) framework and design congruent DCOP formulations with binary constraints which are proven to yield the optimal solution. To approach real-world efficiency requirements, we obtain immense speedups by improving communication structure and precomputing best case bounds. Heuristics for generating better communication structures and calculating bound in a distributed manner are provided and tested on …

Notes On Equilibria In Symmetric Games, Shih-Fen Cheng, Daniel M. Reeves, Yevgeniy Vorobeychik, Michael P. Wellman

Research Collection School Of Computing and Information Systems

In a symmetric game, every player is identical with respect to the game rules. We show that a symmetric 2strategy game must have a pure-strategy Nash equilibrium. We also discuss Nash’s original paper and its generalized notion of symmetry in games. As a special case of Nash’s theorem, any finite symmetric game has a symmetric Nash equilibrium. Furthermore, symmetric infinite games with compact, convex strategy spaces and continuous, quasiconcave utility functions have symmetric pure-strategy Nash equilibria. Finally, we discuss how to exploit symmetry for more efficient methods of finding Nash equilibria.

Review Of The Product Development Process And Information Flow In The Manufacturing Industry: Problems And A Possible Wav Forward, E Opiyo

Tanzania Journal of Engineering and Technology (TJET)

No abstract provided.

Multi-Period Multi-Dimensional Knapsack Problem And Its Application To Available-To-Promise, Hoong Chuin Lau, M. K. Lim

Research Collection School Of Computing and Information Systems

This paper is motivated by a recent trend in logistics scheduling, called Available-to-Promise. We model this problem as the multi-period multi-dimensional knapsack problem. We provide some properties for a special case of a single-dimensional problem. Based on insights obtained from these properties, we propose a two-phase heuristics for solving the multi-dimensional problem. We also propose a novel time-based ant colony optimization algorithm. The quality of the solutions generated is verified through experiments, where we demonstrate that the computational time is superior compared with integer programming to achieve solutions that are within a small percentage of the upper bounds.

Logistics Outsourcing And 3pl Challenges, Michelle L. F. Cheong

Research Collection School Of Computing and Information Systems

Logistics has been an important part of every economy and every business entity. The worldwide trend in globalization has led to many companies outsourcing their logistics function to Third-Party Logistics (3PL) companies, so as to focus on their core competencies. This paper attempts to broadly identify and categorize the challenges faced by 3PL companies and discover potential gaps for future research. Some of the challenges will be related with the experience and information collected from interviews with two 3PL companies.

Task Allocation Via Multi-Agent Coalition Formation: Taxonomy, Algorithms And Complexity, Hoong Chuin Lau, L. Zhang

Research Collection School Of Computing and Information Systems

Coalition formation has become a key topic in multiagent research. In this paper, we propose a preliminary classification for the coalition formation problem based on three driving factors (demands, resources and profit objectives). We divide our analysis into 5 cases. For each case, we present algorithms and complexity results. We anticipate that with future research, this classification can be extended in similar fashion to the comprehensive classification for the job scheduling problem.

Multi-Agent Coalition Via Autonomous Price Negotiation In A Real-Time Web Environment, Hoong Chuin Lau, Wei Sian Lim

Research Collection School Of Computing and Information Systems

In e-marketplaces, customers specify job requests in real-time and agents form coalitions to service them. This paper proposes a protocol for self-interested agents to negotiate prices in forming successful coalitions. We propose and experiment with two negotiation schemes: one allows information sharing while the other does not.

A Generic Object-Oriented Tabu Search Framework, Hoong Chuin Lau, Wee Chong Wan, Xiaomin Jia

Research Collection School Of Computing and Information Systems

Presently, most tabu search designers devise their applications without considering the potential of design and code reuse, which consequently prolong the development of subsequent applications. In this paper, we propose a software solution known as Tabu Search Framework (TSF), which is a generic C++ software framework for tabu search implementation. The framework excels in code recycling through the use of a welldesigned set of generic abstract classes that clearly define their collaborative roles in the algorithm. Additionally, the framework incorporates a centralized process and control mechanism that enhances the search with intelligence. This results in a generic framework that is …

Solving Multi-Objective Multi-Constrained Optimization Problems Using Hybrid Ants System And Tabu Search, Hoong Chuin Lau, Min Kwang Lim, Wee Chong Wan, Hui Wang, Xiaotao Wu

Research Collection School Of Computing and Information Systems

Many real-world optimization problems today are multi-objective multi-constraint generalizations of NP-hard problems. A classic case we study in this paper is the Inventory Routing Problem with Time Windows (IRPTW). IRPTW considers inventory costs across multiple instances of Vehicle Routing Problem with Time Windows (VRPTW). The latter is in turn extended with time-windows constraints from the Vehicle Routing Problem (VRP), which is extended with optimal fleet size objective from the single-objective Traveling Salesman Problem (TSP). While single-objective problems like TSP are solved effectively using meta-heuristics, it is not obvious how to cope with the increasing complexity systematically as the problem is …

A Generic Object-Oriented Tabu Search Framework, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Presently, most tabu search designers devise their applications without considering the potential of design and code reuse, which consequently prolong the development of subsequent applications. In this paper, we propose a software solution known as Tabu Search Framework (TSF), which is a generic C++ software framework for tabu search implementation. The framework excels in code recycling through the use of a welldesigned set of generic abstract classes that clearly define their collaborative roles in the algorithm. Additionally, the framework incorporates a centralized process and control mechanism that enhances the search with intelligence. This results in a generic framework that is …

Pickup And Delivery Problem With Time Windows: Algorithms And Test Case Generation, Hoong Chuin Lau, Zhe Liang

Research Collection School Of Computing and Information Systems

In the pickup and delivery problem with time windows (PDPTW), vehicles have to transport loads from origins to destinations respecting capacity and time constraints. In this paper, we present a two-phase method to solve the PDPTW. In the first phase, we apply a novel construction heuristics to generate an initial solution. In the second phase, a tabu search method is proposed to improve the solution. Another contribution of this paper is a strategy to generate good problem instances and benchmarking solutions for PDPTW, based on Solomon' s benchmark test cases for VRPTW. Experimental results show that our approach yields very …

Integrating Local Search And Network Flow To Solve The Inventory Routing Problem, Hoong Chuin Lau, Q Liu, H. Ono

Research Collection School Of Computing and Information Systems

The inventory routing problem is one of important and practical problems in logistics. It involves the integration of inventory management and vehicle routing, both of which are known to be NP-hard. In this paper, we combine local search and network flows to solve the inventory management problem, by utilizing the minimum cost flow sub-solutions as a guiding measure for local search. We then integrate with a standard VRPTW solver to present experimental results for the overall inventory routing problem, based on instances extended from the Solomon benchmark problems.

A New Approach For Weighted Constraint Satisfaction, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We consider the Weighted Constraint Satisfaction Problem which is an important problem in Artificial Intelligence. Given a set of variables, their domains and a set of constraints between variables, our goal is to obtain an assignment of the variables to domain values such that the weighted sum of satisfied constraints is maximized. In this paper, we present a new approach based on randomized rounding of semidefinite programming relaxation. Besides having provable worst-case bounds for domain sizes 2 and 3, our algorithm is simple and efficient in practice, and produces better solutions than some other polynomial-time algorithms such as greedy and …

Pickup And Delivery Problem With Time Windows: Algorithms And Test Case Generation, Hoong Chuin Lau, Zhe Liang

Research Collection School Of Computing and Information Systems

In the pickup and delivery problem with time windows (PDPTW), vehicles have to transport loads from origins to destinations respecting capacity and time constraints. In this paper, we present a two-phase method to solve the PDPTW. In the first phase, we apply a novel construction heuristics to generate an initial solution. In the second phase, a tabu search method is proposed to improve the solution. Another contribution of this paper is a strategy to generate good problem instances and benchmarking solutions for PDPTW, based on Solomon's benchmark test cases for VRPTW. Experimental results show that our approach yields very good …

A Multi-Agent Framework For Supporting Intelligent Fourth-Party Logistics, Hoong Chuin Lau, G. Lo

Research Collection School Of Computing and Information Systems

A distributed intelligent agent-based framework that supports fourth-party logistics optimization under a web-based e-Commerce environment has been proposed in this paper. In the framework, customer job requests come through an e-Procurement service. These requests are consolidated and pushed to the e-Market Place service periodically. The e-Market Place then serves as a broker that allows intelligent agents to bid to serve these requests optimally in real-time by solving multiple instances of underlying logistics optimization problem. The resulting system was implemented based on the Java 2 Enterprise Edition (J2EE) platform using distributed system technology for communication between objects.

Hopfield Model For Shortest Path Computation And Routing In Atm Network, Chee Weng Lee

Student Works (2000-2009)

This research focuses on the application of Hopfield neural network and Boltmann machine in solving the shortest path routing problem in the ATM network environment. Hopfield neural network and Boltzmann machine are two types of neural network which are commonly used for solving optimization problem such as the shortest path routing problem. The objectives of this research are to construct a Hopfield neural network and a Boltzmann machine for solving the shortest path routing problem in the ATM network. Both of these two types of neural network are built based on a chosen example of an A TM network. The …

Application Of Vibrational Techniques In Determination Of Dynamic Properties Of Agricultural Products-State Of The Arton Of Vibrational Techniques In Determination Of Dynamic Properties Of Agricultural Products-State Of The Art, Silas Kajuna

Tanzania Journal of Engineering and Technology (TJET)

Vibration is one of the techniques employed in the determination of dynamic properties of fruits and vegetables. It entails generation of a mechanical or acoustic vibrational signal which is propagated through the flesh of the agricultural material. A transducer is either attached or held close to the specimen to monitor the propagation of the signal through the specimen. The manner in which the signal is transmitted through the material is analyzed, and the dynamic properties of the specimen which relate to its firmness or its internal being are derived. The technique has been around for the past 30 years or …

Study Of Human Factors Variables In Battle Outcome Prediction Models, David Andrew Glovier

Engineering Management & Systems Engineering Theses & Dissertations

Over time there have been many improvements in models that are used to predict the outcome of battles. Currently there is much supposition and speculation surrounding the use of human performance related factors as additional inputs to battle simulation models to improve their accuracy. However there is no conclusive scientific evidence which shows that these factors do make a significant difference. This study investigates the use of factors that may impact on the human performance directly or indirectly in battle prediction models. These factors consist of traditional human factors and external factors that may influence the human performance. The research …

A Synthesized Methodology For Eliciting Expert Judgment For Addressing Uncertainty In Decision Analysis, Richard W. Monroe

Engineering Management & Systems Engineering Theses & Dissertations

This dissertation describes the development, refinement, and demonstration of an expert judgment elicitation methodology. The methodology has been developed by synthesizing the literature across several social science and scientific fields. The foremost consideration in the methodology development has been to incorporate elements that are based on reasonable expectations for the human capabilities of the user, the expert in this case.

Many methodologies exist for eliciting assessments for uncertain events. These are frequently elicited in probability form. This methodology differs by incorporating a qualitative element as a beginning step for the elicitation process. The qualitative assessment is a more reasonable way …

Exploring Knowledge Processes For Technology Assimilation, Rochelle K. Young

Engineering Management & Systems Engineering Theses & Dissertations

In the emerging knowledge society, the ability to make the experience and expertise of those involved in and affected by new technology unconditionally available to all members of an organization is becoming increasingly important. One of the problems in developing such knowledge processes for technology assimilation is that current social structures do not easily accommodate unconditional participation. Since the implementation of modern information technology is changing the workplace and the nature of work itself, alternative social structures are needed. This research takes as given that deep questions concerning knowledge processes and social transformation are in principle undecidable; and, only questions …

Combinatorial Approaches For Hard Problems In Manpower Scheduling, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Manpower scheduling is concerned with the construction of a workers' schedule which meets demands while satisfying given constraints. We consider a manpower scheduling Problem, called the Change Shift Assignment Problem(CSAP). In previous work, we proved that CSAP is NP-hard and presented greedy methods to solve some restricted versions. In this paper, we present combinatorial algorithms to solve more general and realistic versions of CSAP which are unlikely solvable by greedy methods. First, we model CSAP as a fixed-charge network and show that a feasible schedule can be obtained by finding disjoint paths in the network, which can be derived from …