Open Access. Powered by Scholars. Published by Universities.®

Operations Research, Systems Engineering and Industrial Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

Series

Artificial Intelligence and Robotics

Scheduling

Articles 1 - 8 of 8

Full-Text Articles in Operations Research, Systems Engineering and Industrial Engineering

Orienteering Problem: A Survey Of Recent Variants, Solution Approaches And Applications, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen Dec 2016

Orienteering Problem: A Survey Of Recent Variants, Solution Approaches And Applications, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen

Research Collection School Of Information Systems

The Orienteering Problem (OP) has received a lot of attention in the past few decades. The OP is a routing problem in which the goal is to determine a subset of nodes to visit, and in which order, so that the total collected score is maximized and a given time budget is not exceeded. A number of typical variants has been studied, such as the Team OP, the (Team) OP with Time Windows and the Time Dependent OP. Recently, a number of new variants of the OP was introduced, such as the Stochastic OP, the Generalized OP, the Arc OP ...


Orienteering Problem: A Survey Of Recent Variants, Solution Approaches And Applications, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen Dec 2016

Orienteering Problem: A Survey Of Recent Variants, Solution Approaches And Applications, Aldy Gunawan, Hoong Chuin Lau, Pieter Vansteenwegen

Research Collection School Of Information Systems

The Orienteering Problem (OP) has received a lot of attention in the past few decades. The OP is a routing problem in which the goal is to determine a subset of nodes to visit, and in which order, so that the total collected score is maximized and a given time budget is not exceeded. A number of typical variants has been studied, such as the Team OP, the (Team) OP with Time Windows and the Time Dependent OP. Recently, a number of new variants of the OP was introduced, such as the Stochastic OP, the Generalized OP, the Arc OP ...


Strategic Planning For Setting Up Base Stations In Emergency Medical Systems, Supriyo Ghosh, Pradeep Varakantham Jun 2016

Strategic Planning For Setting Up Base Stations In Emergency Medical Systems, Supriyo Ghosh, Pradeep Varakantham

Research Collection School Of Information Systems

Emergency Medical Systems (EMSs) are an important component of public health-care services. Improving infrastructure for EMS and specifically the construction of base stations at the ”right” locations to reduce response times is the main focus of this paper. This is a computationally challenging task because of the: (a) exponentially large action space arising from having to consider combinations of potential base locations, which themselves can be significant; and (b) direct impact on the performance of the ambulance allocation problem, where we decide allocation of ambulances to bases. We present an incremental greedy approach to discover the placement of bases that ...


Dual Formulations For Optimizing Dec-Pomdp Controllers, Akshat Kumar, Hala Mostafa, Shlomo Zilberstein Jun 2016

Dual Formulations For Optimizing Dec-Pomdp Controllers, Akshat Kumar, Hala Mostafa, Shlomo Zilberstein

Research Collection School Of Information Systems

Decentralized POMDP is an expressive model for multi-agent planning. Finite-state controllers (FSCs)---often used to represent policies for infinite-horizon problems---offer a compact, simple-to-execute policy representation. We exploit novel connections between optimizing decentralized FSCs and the dual linear program for MDPs. Consequently, we describe a dual mixed integer linear program (MIP) for optimizing deterministic FSCs. We exploit the Dec-POMDP structure to devise a compact MIP and formulate constraints that result in policies executable in partially-observable decentralized settings. We show analytically that the dual formulation can also be exploited within the expectation maximization (EM) framework to optimize stochastic FSCs. The resulting EM ...


Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau Jan 2012

Robust Distributed Scheduling Via Time Period Aggregation, Shih-Fen Cheng, John Tajan, Hoong Chuin Lau

Research Collection School Of Information Systems

In this paper, we evaluate whether the robustness of a market mechanism that allocates complementary resources could be improved through the aggregation of time periods in which resources are consumed. In particular, we study a multi-round combinatorial auction that is built on a general equilibrium framework. We adopt the general equilibrium framework and the particular combinatorial auction design from the literature, and we investigate the benefits and the limitation of time-period aggregation when demand-side uncertainties are introduced. By using simulation experiments on a real-life resource allocation problem from a container port, we show that, under stochastic conditions, the performance variation ...


Finding Robust-Under-Risk Solutions For Flowshop Scheduling, Steven O. Kimbrough, Ann Kuo, Hoong Chuin Lau Jul 2011

Finding Robust-Under-Risk Solutions For Flowshop Scheduling, Steven O. Kimbrough, Ann Kuo, Hoong Chuin Lau

Research Collection School Of Information Systems

We propose and explore, in the context of benchmark problems for flowshop scheduling, a risk-based concept of robustness for optimization problems. This risk-based concept is in distinction to, and complements, the uncertainty-based concept employed in the field known as robust optimization. Implementation of our concept requires problem solution methods that sample the solution space intelligently and that produce large numbers of distinct sample points. With these solutions to hand, their robustness scores are easily obtained and heuristically robust solutions found. We find evolutionary computation to be effective for this purpose on these problems.


Decentralized Resource Allocation And Scheduling Via Walrasian Auctions With Negotiable Agents, Huaxing Chen, Hoong Chuin Lau Aug 2010

Decentralized Resource Allocation And Scheduling Via Walrasian Auctions With Negotiable Agents, Huaxing Chen, Hoong Chuin Lau

Research Collection School Of Information Systems

This paper is concerned with solving decentralized resource allocation and scheduling problems via auctions with negotiable agents by allowing agents to switch their bid generation strategies within the auction process, such that a better system wide performance is achieved on average as compared to the conventional walrasian auction running with agents of fixed bid generation strategy. We propose a negotiation mechanism embedded in auctioneer to solicit bidders’ change of strategies in the process of auction. Finally we benchmark our approach against conventional auctions subject to the real-time large-scale dynamic resource coordination problem to demonstrate the effectiveness of our approach.


Efficient Algorithms For Machine Scheduling Problems With Earliness And Tardiness Penalties, Guang Feng, Hoong Chuin Lau Mar 2007

Efficient Algorithms For Machine Scheduling Problems With Earliness And Tardiness Penalties, Guang Feng, Hoong Chuin Lau

Research Collection School Of Information Systems

In this paper, we study the multi-machine scheduling problem with earliness and tardiness penalties and sequence dependent setup times. This problem can be decomposed into two subproblems—sequencing and timetabling. Sequencing focuses on assigning each job to a fixed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling focuses on finding an executable schedule from the semi-schedule via idle-time insertion. Sequencing is strongly NP-hard in general. Although timetabling is polynomial-time solvable, it can become a computational bottleneck if the procedure is executed many times within a larger framework. This paper makes two contributions ...