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%.

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.

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%.

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.

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.

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.