| 1. |
- Björklund, Patrik, et al.
(författare)
-
Optimized planning of frequency hopping in cellular networks
- 2005
-
Ingår i: Computers & Operations Research. - 0305-0548 .- 1873-765X. ; 32:1, s. 169-186
-
Tidskriftsartikel (refereegranskat)abstract
- We consider a generalization of the classical frequency assignment problem. The generalization arises when frequency hopping is used in a cellular network. The planning problem concerns assigning lists of frequencies to blocks of transceivers, such that the total interference is minimized. This problem is considerably more difficult than the classical frequency assignment problem, because of the large number of possible frequency lists. We provide the technical background that motivates our study, and present a mathematical model which includes the classical frequency assignment problem as a special case. We describe a simulated annealing algorithm. The algorithm explores the solution space by solving an integer program in each iteration. We report computational results for real-life and synthesized networks. © 2003 Elsevier Ltd. All rights reserved.
|
|
| 2. |
- Abdul-Jalbar, Beatriz, et al.
(författare)
-
A new heuristic to solve the one-warehouse N-retailer problem
- 2010
-
Ingår i: Computers & Operations Research. - : Elsevier BV. - 0305-0548 .- 1873-765X. ; 37:2, s. 265-272
-
Tidskriftsartikel (refereegranskat)abstract
- We deal with a multi-echelon inventory system in which one warehouse supplies an item to multiple retailers. Customer demand arrives at each retailer at a constant rate. The retailers replenish their inventories from the warehouse that in turn orders from an outside supplier. It is assumed that shortages are not allowed and lead times are negligible. The goal is to determine replenishment policies that minimize the overall cost in the system. We develop a heuristic to compute efficient policies, which also can easily be used in a spreadsheet application. The main idea consists of finding a balance between the replenishment and the inventory holding costs at each installation. This new heuristic we compare with two other approaches proposed in the literature; the computational studies show that in most of the instances generated the new method provides lower costs.
|
|
| 3. |
- Beldar, Pedram, et al.
(författare)
-
Non-identical parallel machines batch processing problem to minimize the makespan : Models and algorithms
- 2024
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 168
-
Tidskriftsartikel (refereegranskat)abstract
- This paper studies a parallel heterogeneous machine batching and scheduling problem in which weighted jobs are first batched, and the batches are then assigned and sequenced on machines of varying capacities. The duration of a batch is the longest time needed to process a job, and the objective is that of minimizing the makespan, or the sum of the batches durations on the machine finishing last. The authors develop polynomial-size mathematical formulations and a variable neighborhood search metaheuristic. Extensive computational results suggest that the flow-based formulation outperforms a compact formulation, despite its larger number of variables. The metaheuristic is capable of producing high-quality solutions within a limited computing time.
|
|
| 4. |
- Carlsson, D., et al.
(författare)
-
Using robust optimization for distribution and inventory planning for a large pulp producer
- 2014
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 44, s. 214-225
-
Tidskriftsartikel (refereegranskat)abstract
- Sodra Cell is a world leading producer of pulp and has a large distribution network for its pulp products. This network includes production mills in Sweden and Norway, terminals in European harbours and inland locations, and many customers. The company uses several transport modes including long chartered vessels, spot vessels, trains, barges and trucks. The company uses a supplier managed inventory with a large proportion of its customers. This makes the logistic planning including transportation and inventory critical, as Sodra Cell has direct responsibility of their customers inventories. However, there is still some uncertainty regarding customer demand and Sodra Cell has traditionally used a safety stock inventory approach to handle this. In this paper, we introduce a robust optimization approach to handle the uncertainty and to establish a distribution plan, together with related inventory management. With this approach there is no need for explicit safety stock levels. This is instead taken into account directly through the robust solution. In the proposed model, we can use practical characterization and historical information on the uncertainty. An important result with this is that we can avoid solutions that are too conservative and costly as in standard robust models. A large case study from Sodra Cell is used to validate the proposed approach against the traditional approach with safety stock. The analysis is based on simulations and it shows that the robust approach is more cost efficient and can be used as a basis in a decision support system.
|
|
| 5. |
- Ecker, Grit, et al.
(författare)
-
Accurate optimization models for interference constrained bandwidth allocation in cellular networks
- 2019
-
Ingår i: Computers & Operations Research. - : PERGAMON-ELSEVIER SCIENCE LTD. - 0305-0548 .- 1873-765X. ; 101
-
Tidskriftsartikel (refereegranskat)abstract
- In cellular networks, the signal-to-interference-plus-noise ratio (SINR) is a key metric for link availability and quality. For network planning purposes, a straightforward modeling unfortunately yields numerically difficult optimization models. Further, given a required data rate of a link, its bandwidth consumption depends nonlinearly on the SINR. In this paper, we develop two novel approaches to jointly model SINR-based link availability and bandwidth requirements accurately. The first approach is a set-wise formulation from a users point of view, while the second one exploits discrete channel quality indicators. We compare these formulations with three known approximate approaches numerically, revealing the clear outperformance of our approaches in terms of exactness. Moreover, since the exact models comprise an exponential number of either variables or constraints, we discuss their pros and cons in a further computational study and develop a more efficient algorithm dealing implicitly with the involved constraints. (C) 2018 Elsevier Ltd. All rights reserved.
|
|
| 6. |
- Flisberg, Patrik, et al.
(författare)
-
A hybrid method based on linear programming and tabu search for routing of logging trucks
- 2009
-
Ingår i: Computers & Operations Research. - : Elsevier BV. - 0305-0548 .- 1873-765X. ; 36:4, s. 1122-1144
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper, we consider an operational routing problem to decide the daily routes of logging trucks in forestry. This industrial problem is difficult and includes aspects such as pickup and delivery with split pickups, multiple products, time windows, several time periods, multiple depots, driver changes and a heterogeneous truck fleet. In addition, the problem size is large and the solution time limited. We describe a two-phase solution approach which transforms the problem into a standard vehicle routing problem with time windows. In the first phase, we solve an LP problem in order to find a destination of flow from supply points to demand points. Based on this solution, we create transport nodes which each defines the origin(s) and destination for a full truckload. In phase two, we make use of a standard tabu search method to combine these transport nodes, which can be considered to be customers in vehicle routing problems, into actual routes. The tabu search method is extended to consider some new features. The solution approach is tested on a set of industrial cases from major forest companies in Sweden.
|
|
| 7. |
- Holmberg, Kaj
(författare)
-
Heuristics for the rural postman problem
- 2010
-
Ingår i: Computers & Operations Research. - : Elsevier BV. - 0305-0548 .- 1873-765X. ; 37:5, s. 981-990
-
Tidskriftsartikel (refereegranskat)abstract
- When addressing the problem of snow removal for secondary roads, a tool for solving the rural postman problem can be very useful. We present some ideas for heuristics for this problem. The heuristics are of the same type as the classical Frederickson heuristic. The ideas concern the order of the main steps in such a method, namely constructing a connected graph with all vertices having even degree, containing all the required edges. We also propose two postprocessing heuristics for improving the tours and removing unnecessary detours. The computational tests show that the ideas are interesting alternatives to the classical approach, and that running times are acceptable. We study problem characteristics that may indicate which method to choose.
|
|
| 8. |
- Horn, Matthias, et al.
(författare)
-
A*-based construction of decision diagrams for a prize-collecting scheduling problem
- 2021
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 126
-
Tidskriftsartikel (refereegranskat)abstract
- Decision diagrams (DDs) have proven to be useful tools in combinatorial optimization. Relaxed DDs represent discrete relaxations of problems, can encode essential structural information in a compact form, and may yield strong dual bounds. We propose a novel construction scheme for relaxed multi-valued DDs for a scheduling problem in which a subset of elements has to be selected from a ground set and the selected elements need to be sequenced. The proposed construction scheme builds upon A search guided by a fast-to-calculate problem-specific dual bound heuristic. In contrast to traditional DD compilation methods, the new approach does not rely on a correspondence of DD layers to decision variables. For the considered kind of problem, this implies that multiple nodes representing the same state at different layers can be avoided, and consequently also many redundant isomorphic substructures. For keeping the relaxed DD compact, a new mechanism for merging nodes in a layer-independent way is suggested. For our prize-collecting job sequencing problem, experimental results show that the DDs from our A -based approach provide substantially better bounds while frequently being an order-ofmagnitude smaller than DDs obtained from traditional compilation methods, given about the same time. To obtain a heuristic solution and a corresponding lower bound, we further propose to construct a restricted DD based on the relaxed one, thereby substantially exploiting already gained information. This approach outperforms a standalone restricted DD construction, basic constraint programming and mixed integer linear programming approaches, and a variable neighborhood search in terms of solution quality on most of our benchmark instances.
|
|
| 9. |
- Karlsson, Emil, 1990-, et al.
(författare)
-
Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling
- 2022
-
Ingår i: Computers & Operations Research. - : Elsevier. - 0305-0548 .- 1873-765X. ; 146
-
Tidskriftsartikel (refereegranskat)abstract
- Pre-runtime scheduling of large-scale electronic systems, as those in modern aircraft, can be computationally challenging. In this paper, we study a distributed integrated modular avionic system of practical relevance where the scheduling includes to assign communication messages to time slots and to sequence tasks on modules. For this problem, the challenge is the huge number of tasks to be scheduled and the intricate interaction between the communication and task scheduling. We present a method based on Logic-Based Benders Decomposition (LBBD) to solve this problem. In a master problem, formulated as a mixed-integer program, communication messages are assigned to time slots and in a subproblem, formulated as a constraint program, tasks are scheduled.Our LBBD scheme is accelerated by using cut strengthening, a subproblem relaxation, and components for preprocessing and initialisation of the scheme. The cut strengthening is of the kind that systematically investigates subsets of variables to include in the cut by solving additional subproblems. To further enhance the efficiency of the scheme, we propose a new strategy that extends cut strengthening to also try to construct feasible solutions by using information from solving the additional subproblems. Our computational evaluation is based on publicly available instances with up to 2530 messages and 54,731 tasks. It shows that our method outperforms previous methods for the problem with respect to both solution times and RAM usage. A further evaluation of the different components in the method shows that our new acceleration strategy is important to achieve these results.
|
|
| 10. |
- Larsson, Torbjörn, et al.
(författare)
-
Subbens checklist
- 2016
-
Ingår i: Computers & Operations Research. - : PERGAMON-ELSEVIER SCIENCE LTD. - 0305-0548 .- 1873-765X. ; 71, s. 163-164
-
Tidskriftsartikel (refereegranskat)abstract
- Excellent guides on academic writing and presentation in science in general, and in mathematics and computer science in particular, do abound (see, for example, Refs. [1-8], while guides on the assessment of the results of academic writing are rather more scarce. This short article presents two itemized lists that may be helping hands during the assessment of a scientific article in the field of mathematical optimization and operations research-be it your own, a work by a Master or PhD student of yours, or even a manuscript that you are refereeing for a scientific journal or conference proceedings volume. The first list-"Subbens checklist"-describes necessary ingredients of a complete article. The second list provides criteria for assessing the quality and scientific value of an article. (C) 2016 Elsevier Ltd. All rights reserved.
|
|
