- Title
- A branch-and-bound algorithm for scheduling unit processing time arc shutdown jobs to maximize flow through a transshipment node over time
- Creator
- Boland, N.; Kaur, S.
- Relation
- 20th International Congress on Modelling and Simulation (MODSIM2013). Proceedings of the 20th International Congress on Modelling and Simulation (Adelaide, S.A. 1-6 December, 2013) p. 3295-3301
- Relation
- http://www.mssanz.org.au/modsim2013/
- Publisher
- Modelling and Simulation Society of Australia and New Zealand (MSSANZ)
- Resource Type
- conference paper
- Date
- 2013
- Description
- Many real world complex problems can be viewed as networks with arc capacities, for example, rail networks, or supply chains, in which system throughput needs to be maximized. Arcs in such a network represent important components of the corresponding system, the condition of which may degrade over time. Maintenance of these components (arcs of the network) is important to maintain their productivity. But every maintenance activity incurs some loss of productivity as the arc will be unavailable during its maintenance. To obtain maximum throughput, it is important to select the schedule that leads to minimum loss of flow. In this paper we discuss optimization models for scheduling arc maintenance so as to maximize the throughput of the network, and focus on the case in which each maintenance task requires a single period and the network has a single transshipment node. We note that even this case is strongly NP-hard. Mathematically the problem is defined over a network N = (V, A, s, t, u) with node set V, arc set A, source s ∈ V, sink t ∈ V and nonnegative integral capacity vector u = (ua) a∈A. We permit parallel arcs, i.e. there may exist more than one arc in A having the same start and end node. By dδ¯(v) and dδ+ (v) we denote the set of incoming and outgoing arcs of node v, respectively. We consider this network over a set of T time periods indexed by the set [T] := {1, 2, . . . ,T }, and our objective is to maximize the total flow from s to t. In addition, we are given a subset J ⊆ A of arcs that have to be shut down for exactly one time period in the time horizon. In other words, there is a set of maintenance jobs, one for each arc in J, each with unit processing time. Our optimization problem is to choose these outage time periods in such a way that the total flow from s to t is maximized. More formally, this can be written as a mixed binary program as follows: (formula could not be replicated: see full text) where xai ≥ 0 for a ∈ A and i ∈ [T] denotes the flow on arc a in time period i, and yai ∈ {0, 1} for a ∈ J and i ∈ [T] indicates when the arc a is not shut down for maintenance in time period i. We present a branch-and-bound algorithm called the "Partial-State algorithm" to solve the problem for single transhipment node networks i.e. networks with |V| = 3. Unit processing time of each job leads to formation of symmetries in the solution space. We include powerful symmetry breaking rules in the algorithm to make it more efficient. We provide an easily-computer combinatorial expression that is proved to give the value of LP-relaxation of the problem at each node of the branch-and-bound tree. We also provide another upper bound which is even stronger than the LP value at each node of the tree, and show how this improves the run time of the algorithm.
- Subject
- network models; maintenance scheduling; mixed integer programming; branch and bound
- Identifier
- http://hdl.handle.net/1959.13/1308695
- Identifier
- uon:21703
- Identifier
- ISBN:9780987214331
- Language
- eng
- Reviewed
- Hits: 2342
- Visitors: 2296
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|