|   | 
Details
   web
Records
Author Averbakh, I.; Pereira, J
Title Tree optimization based heuristics and metaheuristics in network construction problems Type
Year 2021 Publication Computers & Operations Research Abbreviated Journal Comput. Oper. Res.
Volume 128 Issue Pages 105190
Keywords Network design; Scheduling; Network construction; Heuristics; Metaheuristics; Local search
Abstract We consider a recently introduced class of network construction problems where edges of a transportation network need to be constructed by a server (construction crew). The server has a constant construction speed which is much lower than its travel speed, so relocation times are negligible with respect to construction times. It is required to find a construction schedule that minimizes a non-decreasing function of the times when various connections of interest become operational. Most problems of this class are strongly NP-hard on general networks, but are often tree-efficient, that is, polynomially solvable on trees. We develop a generic local search heuristic approach and two metaheuristics (Iterated Local Search and Tabu Search) for solving tree-efficient network construction problems on general networks, and explore them computationally. Results of computational experiments indicate that the methods have excellent performance.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0305-0548 ISBN Medium
Area Expedition Conference
Notes WOS:000632975100009 Approved
Call Number UAI @ alexi.delcanto @ Serial 1362
Permanent link to this record
 

 
Author Averbakh, I.; Pereira, J.
Title Lateness Minimization in Pairwise Connectivity Restoration Problems Type
Year 2018 Publication Informs Journal On Computing Abbreviated Journal INFORMS J. Comput.
Volume 30 Issue 3 Pages 522-538
Keywords combinatorial optimization; networks: scheduling; programming: branch and bound; network restoration; network construction; integrated network design and scheduling
Abstract A network is given whose edges need to be constructed (or restored after a disaster). The lengths of edges represent the required construction/restoration times given available resources, and one unit of length of the network can be constructed per unit of time. All points of the network are accessible for construction at any time. For each pair of vertices, a due date is given. It is required to find a construction schedule that minimizes the maximum lateness of all pairs of vertices, where the lateness of a pair is the difference between the time when the pair becomes connected by an already constructed path and the pair's due date. We introduce the problem and analyze its structural properties, present a mixed-integer linear programming formulation, develop a number of lower bounds that are integrated in a branch-and-bound algorithm, and discuss results of computational experiments both for instances based on randomly generated networks and for instances based on 2010 Chilean earthquake data.
Address [Averbakh, Igor] Univ Toronto Scarborough, Dept Management, Toronto, ON M1C 1A4, Canada, Email: averbakh@utsc.uturonto.ca;
Corporate Author Thesis
Publisher Informs Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1091-9856 ISBN Medium
Area Expedition Conference
Notes WOS:000449096000008 Approved
Call Number UAI @ eduardo.moreno @ Serial 924
Permanent link to this record
 

 
Author Barrera, J.; Carrasco, R.A.; Mondschein, S.; Canessa, G.; Rojas-Zalazar, D.
Title Operating room scheduling under waiting time constraints: the Chilean GES plan Type
Year 2020 Publication Annals Of Operations Research Abbreviated Journal Ann. Oper. Res.
Volume 286 Issue 1-2 Pages 501-527
Keywords Scheduling; Operating theater; Operating room scheduling
Abstract In 2000, Chile introduced profound health reforms to achieve a more equitable and fairer system (GES plan). The reforms established a maximum waiting time between diagnosis and treatment for a set of diseases, described as an opportunity guarantee within the reform. If the maximum waiting time is exceeded, the patient is referred to another (private) facility and receives a voucher to cover the additional expenses. This voucher is paid by the health provider that had to do the procedure, which generally is a public hospital. In general, this reform has improved the service for patients with GES pathologies at the expense of patients with non-GES pathologies. These new conditions create a complicated planning scenario for hospitals, in which the hospital's OR Manager must balance the fulfillment of these opportunity guarantees and the timely service of patients not covered by the guarantee. With the collaboration of the Instituto de Neurocirugia, in Santiago, Chile, we developed a mathematical model based on stochastic dynamic programming to schedule surgeries in order to minimize the cost of referrals to the private sector. Given the large size of the state space, we developed an heuristic to compute good solutions in reasonable time and analyzed its performance. Our experimental results, with both simulated and real data, show that our algorithm performs close to optimum and improves upon the current practice. When we compared the results of our heuristic against those obtained by the hospital's OR manager in a simulation setting with real data, we reduced the overtime from occurring 21% of the time to zero, and the non-GES average waiting list's length from 71 to 58 patients, without worsening the average throughput.
Address [Barrera, Javiera; Carrasco, Rodrigo A.; Mondschein, Susana; Canessa, Gianpiero] Univ Adolfo Ibanez, Fac Engn & Sci, Santiago, Chile, Email: javiera.barrera@uai.cl;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0254-5330 ISBN Medium
Area Expedition Conference
Notes WOS:000511564300021 Approved
Call Number UAI @ eduardo.moreno @ Serial 1104
Permanent link to this record
 

 
Author Carrasco, R.A.; Iyengar, G.; Stein, C.
Title Resource cost aware scheduling Type
Year 2018 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 269 Issue 2 Pages 621-632
Keywords Scheduling; Approximation algorithms; Resource aware scheduling; Speed-scaling
Abstract We are interested in the scheduling problem where there are several different resources that determine the speed at which a job runs and we pay depending on the amount of each resource that we use. This work is an extension of the resource dependent job processing time problem and the energy aware scheduling problems. We develop a new constant factor approximation algorithm for resource cost aware scheduling problems: the objective is to minimize the sum of the total cost of resources and the total weighted completion time in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and release dates. Our algorithm handles general job-dependent resource cost functions. We also analyze the practical performance of our algorithms, showing that it is significantly superior to the theoretical bounds and in fact it is very close to optimal. The analysis is done using simulations and real instances, which are left publicly available for future benchmarks. We also present additional heuristic improvements and we study their performance in other settings. (C) 2018 Elsevier B.V. All rights reserved.
Address [Carrasco, Rodrigo A.] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: rax@uai.cl;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0377-2217 ISBN Medium
Area Expedition Conference
Notes WOS:000432502600016 Approved
Call Number UAI @ eduardo.moreno @ Serial 871
Permanent link to this record
 

 
Author Cohen, YM.; Keskinocak, P.; Pereira, J.
Title A note on the flowtime network restoration problem Type
Year 2021 Publication IISE Transactions Abbreviated Journal IISE Trans.
Volume Early Access Issue Pages
Keywords Scheduling; network construction planning; emergency restoration operations; deliveryman problem; traveling repairman problem
Abstract The flowtime network restoration problem was introduced by Averbakh and Pereira (2012) who presented a Minimum Spanning Tree heuristic, two local search procedures, and an exact branch-and-bound algorithm. This note corrects the computational results in Averbakh and Pereira (2012).
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 2472-5854 ISBN Medium
Area Expedition Conference
Notes WOS:000617722200001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1343
Permanent link to this record
 

 
Author Espinoza, D.; Goycoolea, M.; Moreno, E.; Newman, A.
Title MineLib: a library of open pit mining problems Type
Year 2013 Publication Annals Of Operations Research Abbreviated Journal Ann. Oper. Res.
Volume 206 Issue 1 Pages 93-114
Keywords Mine scheduling; Mine planning; Open pit production scheduling; Surface mine production scheduling; Problem libraries; Open pit mining library
Abstract Similar to the mixed-integer programming library (MIPLIB), we present a library of publicly available test problem instances for three classical types of open pit mining problems: the ultimate pit limit problem and two variants of open pit production scheduling problems. The ultimate pit limit problem determines a set of notional three-dimensional blocks containing ore and/or waste material to extract to maximize value subject to geospatial precedence constraints. Open pit production scheduling problems seek to determine when, if ever, a block is extracted from an open pit mine. A typical objective is to maximize the net present value of the extracted ore; constraints include precedence and upper bounds on operational resource usage. Extensions of this problem can include (i) lower bounds on operational resource usage, (ii) the determination of whether a block is sent to a waste dump, i.e., discarded, or to a processing plant, i.e., to a facility that derives salable mineral from the block, (iii) average grade constraints at the processing plant, and (iv) inventories of extracted but unprocessed material. Although open pit mining problems have appeared in academic literature dating back to the 1960s, no standard representations exist, and there are no commonly available corresponding data sets. We describe some representative open pit mining problems, briefly mention related literature, and provide a library consisting of mathematical models and sets of instances, available on the Internet. We conclude with directions for use of this newly established mining library. The library serves not only as a suggestion of standard expressions of and available data for open pit mining problems, but also as encouragement for the development of increasingly sophisticated algorithms.
Address [Espinoza, Daniel] Univ Chile, Dept Ind Engn, Santiago Ctr, Santiago, Chile, Email: daespino@dii.uchile.cl;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0254-5330 ISBN Medium
Area Expedition Conference
Notes WOS:000320694000006 Approved
Call Number UAI @ eduardo.moreno @ Serial 290
Permanent link to this record
 

 
Author Letelier, O.R.; Espinoza, D.; Goycoolea, M.; Moreno, E.; Munoz, G.
Title Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach Type
Year 2020 Publication Operations Research Abbreviated Journal Oper. Res.
Volume 68 Issue 5 Pages 1425-1444
Keywords open pit mining; production scheduling; column generation; heuristics; cutting planes; integer programming applications
Abstract Given a discretized representation of an ore body known as a block model, the open pit mining production scheduling problem that we consider consists of defining which blocks to extract, when to extract them, and how or whether to process them, in such a way as to comply with operational constraints and maximize net present value. Although it has been established that this problem can be modeled with mixed-integer programming, the number of blocks used to represent real-world mines (millions) has made solving large instances nearly impossible in practice. In this article, we introduce a new methodology for tackling this problem and conduct computational tests using real problem sets ranging in size from 20,000 to 5,000,000 blocks and spanning 20 to 50 time periods. We consider both direct block scheduling and bench-phase scheduling problems, with capacity, blending, and minimum production constraints. Using new preprocessing and cutting planes techniques, we are able to reduce the linear programming relaxation value by up to 33%, depending on the instance. Then, using new heuristics, we are able to compute feasible solutions with an average gap of 1.52% relative to the previously computed bound. Moreover, after four hours of running a customized branch-and-bound algorithm on the problems with larger gaps, we are able to further reduce the average from 1.52% to 0.71%.
Address [Rivera Letelier, Orlando] Univ Adolfo Ibanez, Doctoral Program Ind Engn & Operat Res, Santiago 7941169, Chile, Email: orlando.rivera@uai.cl;
Corporate Author Thesis
Publisher Informs Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0030-364x ISBN Medium
Area Expedition Conference
Notes WOS:000574409100008 Approved
Call Number UAI @ alexi.delcanto @ Serial 1250
Permanent link to this record
 

 
Author Mejia, G.; Pereira, J.
Title Multiobjective scheduling algorithm for flexible manufacturing systems with Petri nets Type
Year 2020 Publication Journal Of Manufacturing Systems Abbreviated Journal J. Manuf. Syst.
Volume 54 Issue Pages 272-284
Keywords Machine scheduling; Multi-objective optimization; Petri nets
Abstract In this work, we focus on general multi-objective scheduling problems that can be modeled using a Petri net framework. Due to their generality, Petri nets are a useful abstraction that captures multiple characteristics of real-life processes. To provide a general solution procedure for the abstraction, we propose three alternative approaches using an indirect scheme to represent the solution: (1) a genetic algorithm that combines two objectives through a weighted fitness function, (2) a non dominated sorting genetic algorithm (NSGA-II) that explicitly addresses the multi-objective nature of the problem and (3) a multi-objective local search approach that simultaneously explores multiple candidate solutions. These algorithms are tested in an extensive computational experiment showing the applicability of this general framework to obtain quality solutions.
Address [Mejia, Gonzalo] Univ La Sabana, Fac Engn, Campus Puente del Comun, Chia, Colombia, Email: gonzalo.mejia@unisabana.edu.co;
Corporate Author Thesis
Publisher Elsevier Sci Ltd Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0278-6125 ISBN Medium
Area Expedition Conference
Notes WOS:000521511500021 Approved
Call Number UAI @ eduardo.moreno @ Serial 1154
Permanent link to this record
 

 
Author Osorio-Valenzuela, L.; Pereira, J.; Quezada, F.; Vasquez, O.C.
Title Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints Type
Year 2019 Publication Applied Mathematical Modelling Abbreviated Journal Appl. Math. Model.
Volume 74 Issue Pages 512-527
Keywords Scheduling; Parallel machines; Interval and workload constraints; Branch-and-price
Abstract In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-andprice approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem. (C) 2019 Elsevier Inc. All rights reserved.
Address [Osorio-Valenzuela, Luis] Univ Santiago Chile, Elect Engn Dept, Santiago, Chile, Email: luis.osoriov@usach.cl;
Corporate Author Thesis
Publisher Elsevier Science Inc Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0307-904x ISBN Medium
Area Expedition Conference
Notes WOS:000474317800031 Approved
Call Number UAI @ eduardo.moreno @ Serial 1013
Permanent link to this record
 

 
Author Pereira, J.
Title The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective Type
Year 2016 Publication Computers & Operations Research Abbreviated Journal Comput. Oper. Res.
Volume 66 Issue Pages 141-152
Keywords Scheduling; Single machine; Uncertainty; Robust optimization; Branch-and-bound
Abstract Single machine scheduling is a classical optimization problem that depicts multiple real life systems in which a single resource (the machine) represents the whole system or the bottleneck operation of the system. In this paper we consider the problem under a weighted completion time performance metric in which the processing time of the tasks to perform (the jobs) are uncertain, but can only take values from closed intervals. The objective is then to find a solution that minimizes the maximum absolute regret for any possible realization of the processing times. We present an exact branch-and-bound method to solve the problem, and conduct a computational experiment to ascertain the possibilities and limitations of the proposed method. The results show that the algorithm is able to optimally solve instances of moderate size (25-40 jobs depending on the characteristics of the instance). (c) 2015 Elsevier Ltd. All rights reserved.
Address [Pereira, Jordi] Univ Adolfo Ibanez, Fac Sci & Engn, Vina Del Mar, Chile, Email: jorge.pereira@uai.cl
Corporate Author Thesis
Publisher Pergamon-Elsevier Science Ltd Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0305-0548 ISBN Medium
Area Expedition Conference
Notes WOS:000366779900013 Approved
Call Number UAI @ eduardo.moreno @ Serial 558
Permanent link to this record
 

 
Author Pereira, J.; Vasquez, O.C.
Title The single machine weighted mean squared deviation problem Type
Year 2017 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 261 Issue 2 Pages 515-529
Keywords Scheduling; Single machine; JIT; Branch-and-cut; Dominance properties
Abstract This paper studies a single machine problem related to the just-In-Time (JIT) production objective in which the goal is to minimize the sum of weighted mean squared deviation of the completion times with respect to a common due date. In order to solve the problem, several structural and dominance properties of the optimal solution are investigated. These properties are then integrated within a branch and-cut approach to solve a time-indexed formulation of the problem. The results of a computational experiment with the proposed algorithm show that the method is able to optimally solve instances with up to 300 jobs within reduced running times, improving other integer programming approaches. (C) 2017 Elsevier B.V. All rights reserved.
Address [Pereira, Jordi] Univ Adolfo Ibanez, Dept Engn & Sci, Av Padre Hurtado 750,Off C216, Vina Del Mar, Chile, Email: jorge.pereira@uai.cl;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0377-2217 ISBN Medium
Area Expedition Conference
Notes WOS:000401206300009 Approved
Call Number UAI @ eduardo.moreno @ Serial 730
Permanent link to this record
 

 
Author Reus, L.; Belbeze, M.; Feddersen, H.; Rubio, E.
Title Extraction Planning Under Capacity Uncertainty at the Chuquicamata Underground Mine Type
Year 2018 Publication Interfaces Abbreviated Journal Interfaces
Volume 48 Issue 6 Pages 543-555
Keywords underground mine extraction scheduling; operational uncertainty management; stochastic programming applications; long-term mine planning
Abstract We propose an extraction schedule for the Chuquicamata underground copper mine in Chile. The schedule maximizes profits while adhering to all operational and geomechanical requirements involved in proper removal of the material. We include extraction capacity uncertainties due to failure in equipment, specifically to the overland conveyor, which we find to be the most critical component in the extraction process. First we present the extraction plan based on a deterministic model, which does not assume uncertainty in the extraction capacity and represents the solution that the mine can implement without using the results of this study. Then we extend this model to a stochastic setting by generating different scenarios for capacity values in subsequent periods. We construct a multistage model that handles economic downside risk arising from this uncertainty by penalizing plans that deviate from an ex ante profit target in one or more scenarios. Simulation results show that a stochastic-based solution can achieve the same expected profits as the deterministic-based solution. However, the earnings of the stochastic-based solution average 5% more for scenarios in which earnings are below the 10th percentile. If we choose a target 2% below the expected profit obtained by the deterministic-based solution, this average increases from 5% to 9%.
Address [Reus, Lorenzo; Belbeze, Mathias; Feddersen, Hans] Adolfo Ibanez Univ, Dept Engn & Sci, Santiago 7910000, Chile, Email: lorenzo.reus@uai.cl;
Corporate Author Thesis
Publisher Informs Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0092-2102 ISBN Medium
Area Expedition Conference
Notes WOS:000454513500005 Approved
Call Number UAI @ eduardo.moreno @ Serial 967
Permanent link to this record
 

 
Author Yushimito, W.F.; Ban, X.G.; Holguin-Veras, J.
Title Correcting the Market Failure in Work Trips with Work Rescheduling: An Analysis Using Bi-level Models for the Firm-workers Interplay Type
Year 2015 Publication Networks & Spatial Economics Abbreviated Journal Netw Spat. Econ.
Volume 15 Issue 3 Pages 883-915
Keywords Peak congestion; Rescheduling of work; Market failure; Bi-level models; Stackelberg; Dynamic traffic assignment
Abstract Compulsory trips (e.g., work trips) contribute with the major part of the congestion in the morning peak. It also prevents the society to reach a social optimum (the solution that maximizes welfare) because the presence of the private utility of one the agents (the firm), acting as a dominant agent, does not account for the additional costs imposed in their workers (congestion) as well as the costs imposed to the rest of the society (i.e., congestion, pollution). In this paper, a study of a strategy to influence the demand generator by relaxing the arrival constraints is presented. Bi-level programming models are used to investigate the equilibrium reached from the firm-workers interplay which helps to explain how the market failure arises. The evaluation includes the use of incentives to induce the shift to less congested periods and the case of the social system optimum in which a planner objective is incorporated as a third agent usually seeking to improve social welfare (improve productivity of the firm while at the same time reduce the total system travel time). The later is used to show that it is possible to provide a more efficient solution which better off society. A numerical example is used to (1) show the nature of the market failure, (2) evaluate the social system optimum, and (3) show how a congestion tax or an optimal incentive can help to correct the market failure. The results also corroborate that these mechanisms are more likely to be more efficient when firms face little production effects on time and workers do not high opportunity costs for starting at off peak periods.
Address [Yushimito, Wilfredo F.] Univ Adolfo Ibanez, Dept Sci & Engn, Vina Del Mar, Chile, Email: wilfredo.yushimito@uai.cl;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1566-113x ISBN Medium
Area Expedition Conference
Notes WOS:000364529500023 Approved
Call Number UAI @ eduardo.moreno @ Serial 622
Permanent link to this record