2012 Program

The default venue for the monthly lectures is RMIT, Access Grid Room. 8.9.66

Melbourne time

---

• 41st Annual Report, March 21, 2012.


• 2011 Program


• 2010 Program


• 2009 Program

Scheduled Events for 2012

Date	Speaker	Topic
April 18, 6:00PM	Hanyu Gu	An improved Lagrangian relaxation method for maximising the net present value of large resource-constrained projects
March 21, 5:30PM	Martin Savelsbergh	AGM (5:30) and a Lecture (6:00PM): Incremental Network Design with Shortest Paths
Feb 15, 6:00PM	Andreas Ernst and Gaurav Singh	Lagrangian Particle Swarm Optimization for a Resource Constrained Machine Scheduling Problem

Venue: RMIT Access Grid Room, 8.9.66 (Building 8, level 9, room 66)

Time: 6:00PM, Wed April 18, 2012

Program: Lecture by Hanyu Gu*, NICTA

Topic:: An improved Lagrangian relaxation method for maximising the net present value of large resource-constrained projects

Abstract
In this talk we discuss about the application of Lagrangian relaxation method for maximising the net present value of large resource-constrained projects. Large industrial applications can require thousands of activities to be scheduled over a long time span. The largest case we have (from a mining company) includes about 11,000 activities spanning over 20 years. Our experiences show that the direct application of the techniques in literature cannot deal with problems on this scale. The main obstacle is that the Lagrangian relaxation problem cannot be solved efficiently as a maximal flow problem. To overcome this issue we relax some precedence constraints so that activities can form clusters that are independent from each other. Our goal here is to relax as fewer as possible the precedence constraints but still obtain activity clusters small enough to be solved efficiently. Another difficulty is that the Lagrangian dual problem converges more slowly due to the high dimensions. A hierarchical scheme is proposed to accelerate the convergence using a simple bundle algorithm. Some implementation issue will also be discussed. We give some preliminary results on the stope scheduling problems ranging from 1400 to 11000 activities.

---

Biography: Dr. Hanyu Gu is a researcher of National ICT Australia, Victoria Research Laboratory. Before he joined NICTA, he had been working on airline scheduling problems for a Melbourne based software company. He is now working on the decomposition methods for large industrial optimisation problems under the G12 project.

*: The presentation is based on joint work with Mark Wallace and Peter J. Stuckey.

---

Venue: RMIT Access Grid Room, 8.9.66 (Building 8, level 9, room 66)

Time: 5:30PM, Wed March 21, 2012

Program:
AGM (5:30PM): 41st Annual Report, March 21, 2012

Lecture (6:00PM) by Martin Savelsbergh, University of Newcastle
Topic of lecture:: Incremental Network Design with Shortest Paths

Abstract
Network infrastructures are a common phenomenon. Network upgrades and expansions typically occur over time due to budget constraints. We introduce a class of incremental network design problems that allow investigation of many of the key issues related to the choice and timing of infrastructure expansions and their impact on the costs of the activities performed on that infrastructure. We focus on the simplest variant: incremental network design with shortest paths, and show that even its simplest variant is NP-hard. We investigate structural properties of optimal solutions, we analyze the worst-case performance of natural greedy heuristics, we derive a 4-approximation algorithm, and we present an integer program formulation and conduct a small computational study.

Joint work with Matthew Baxter, Tarek Elgindy and Andreas Ernst (CSIRO Mathematics Informatics and Statistics) and Thomas Kalinowski (Institute for Mathematics University of Rostock, Germany).

---

Venue: RMIT Access Grid Room, 8.9.66 (Building 8, level 9, room 66)

Time: 6:00PM, Wed Feb 16, 2012

Program: Lecture by Andreas Ernst and Gaurav Singh, CSIRO

Topic:: Lagrangian Particle Swarm Optimization for a Resource Constrained Machine Scheduling Problem

Abstract
Recently a novel hybrid heuristic combining various Lagrangian heuristic ideas with Particle Swarm Optimization has been proposed and tested in the context of degree constrained minimum spanning trees. This paper investigates the applicability of the new hybrid meta-heuristic to a challenging scheduling problem. The resource constrained scheduling problem involves a set of jobs that need to be scheduled on multiple machines so as to minimise total weighted tardiness in the presence of precedence constraints and release dates. This is further complicated by the need for the jobs to consume a shared resource with limited capacity. The paper shows that the Lagrangian Particle Swarm Optimization approach can produce both high quality upper bounds (heuristic solutions) and useful lower bounds giving a performance guarantee for these heuristic solutions. Computational results are presented to show that the new method can outperform previous approaches in the literature for this problem.