Home  << 1 >> 
Averbakh, I., & Pereira, J. (2021). Tree optimization based heuristics and metaheuristics in network construction problems. Comput. Oper. Res., 128, 105190.
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 nondecreasing function of the times when various connections of interest become operational. Most problems of this class are strongly NPhard on general networks, but are often treeefficient, 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 treeefficient network construction problems on general networks, and explore them computationally. Results of computational experiments indicate that the methods have excellent performance.
Keywords: Network design; Scheduling; Network construction; Heuristics; Metaheuristics; Local search

Averbakh, I., & Pereira, J. (2018). Lateness Minimization in Pairwise Connectivity Restoration Problems. INFORMS J. Comput., 30(3), 522–538.
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 mixedinteger linear programming formulation, develop a number of lower bounds that are integrated in a branchandbound algorithm, and discuss results of computational experiments both for instances based on randomly generated networks and for instances based on 2010 Chilean earthquake data.

Azar, M., Carrasco, R. A., & Mondschein, S. (2022). Dealing with Uncertain Surgery Times in Operating Room Scheduling. Eur. J. Oper. Res., 299(1), 377–394.
Abstract: The operating theater is one of the most expensive units in the hospital, representing up to 40% of the total expenses. Because of its importance, the operating room scheduling problem has been addressed from many different perspectives since the early 1960s. One of the main difficulties that
has reduced the applicability of the current results is the high variability in surgery duration, making schedule recommendations hard to implement. In this work, we propose a timeindexed scheduling formulation to solve the operational problem. Our main contribution is that we propose the use of chance constraints related to the surgery duration's probability distribution for each surgeon to improve the scheduling performance. We show how to implement these chance constraints as linear ones in our timeindexed formulation, enhancing the performance of the resulting schedules significantly. Through data analysis of real historical instances, we develop specific constraints that improve the schedule, reducing the need for overtime without affecting the utilization significantly. Furthermore, these constraints give the operating room manager the possibility of balancing overtime and utilization through a tunning parameter in our formulation. Finally, through simulations and the use of real instances, we report the performance for four different metrics, showing the importance of using historical data to get the right balance between the utilization and overtime. 
Barrera, J., Carrasco, R. A., Mondschein, S., Canessa, G., & RojasZalazar, D. (2020). Operating room scheduling under waiting time constraints: the Chilean GES plan. Ann. Oper. Res., 286(12), 501–527.
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 nonGES 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 nonGES average waiting list's length from 71 to 58 patients, without worsening the average throughput.
Keywords: Scheduling; Operating theater; Operating room scheduling

BeyaMarshall, V., Arcos, E., Seguel, O., Galleguillos, M., & Kremer, C. (2022). Optimal irrigation management for avocado (cv. 'Hass') trees by monitoring soil water content and plant water status. Agric. Water Manag., 271, 107794.
Abstract: Irrigation scheduling based on soil water content (Ow) sensors requires that Ow be maintained within a range (management lines) that is optimal for plant growth. The lower limit or “breaking point ” is determined following the soil water content dynamics on the transition of a rapid rate of depletion to a slower, under similar reference evapotranspiration. Although this criterion is practical, its implementation should be validated with plant water status measurement that contemplate weather condition, such as stem water potential “nonstressed ” baseline (Tx as a function of vaporpressure deficit (VPD) in Ow conditions that do not limit yield). A study was conducted on a mature cv. 'Hass' avocado orchard in Central Chile during two seasons. There were 5 irrigation treatments: T1, Control; T2 and T3 with 29% less and 25% more of what was applied in T1, respectively; T4 and T5 same as Control until first and second fruit drop abscission, respectively, and then with 29% less. T1 trees were irrigated using a continuous frequency domain reflectometry (FDR) probe to maintain the root zone between field capacity and the breaking point. There was biweekly monitoring of the Ow prior to irrigation, Tx and VPD. The Tx decline proportional to the intensity and the timing of water restriction; however, no treatment affected the crop load in either season. T2 did not show significant detrimental in fruit size, production and maturation, despite that frequently reached water content levels at the limit of the breaking point, and showed lower levels of stem water potential than Control, being the treatment with the highest water productivity. The results confirm that breaking point is an effective criterion to establish irrigation management. Additionally, when comparing the baseline for our nonstressed trees with a baseline from full irrigation treatments obtained from the literature, 30% water savings were achieved.

Carrasco, R. A., Iyengar, G., & Stein, C. (2018). Resource cost aware scheduling. Eur. J. Oper. Res., 269(2), 621–632.
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 nonpreemptive setting, allowing for arbitrary precedence constraints and release dates. Our algorithm handles general jobdependent 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.

Cohen, Y. M., Keskinocak, P., & Pereira, J. (2021). A note on the flowtime network restoration problem. IISE Trans., 53(12), 1351–1352.
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 branchandbound algorithm. This note corrects the computational results in Averbakh and Pereira (2012).

Espinoza, D., Goycoolea, M., Moreno, E., & Newman, A. (2013). MineLib: a library of open pit mining problems. Ann. Oper. Res., 206(1), 93–114.
Abstract: Similar to the mixedinteger 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 threedimensional 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.

HomemdeMello, T., Kong, Q. X., & GodoyBarba, R. (2022). A Simulation Optimization Approach for the Appointment Scheduling Problem with DecisionDependent Uncertainties. INFORMS J. Comput., Early Access.
Abstract: The appointment scheduling problem (ASP) studies how to manage patient arrivals to a healthcare system to improve system performance. An important challenge occurs when some patients may not show up for an appointment. Although the ASP is well studied in the literature, the vast majority of the existing work does not consider the wellobserved phenomenon that patient noshow is influenced by the appointment time, the usual decision variable in the ASP. This paper studies the ASP with random service time (exogenous uncertainty) with known distribution and patient decisiondependent noshow behavior (endogenous uncertainty). This problem belongs to the class of stochastic optimization with decisiondependent uncertainties. Such problems are notoriously difficult as they are typically nonconvex. We propose a stochastic projected gradient path (SPGP) method to solve the problem, which requires the development of a gradient estimator of the objective functiona nontrivial task, as the literature on gradientbased optimization algorithms for problems with decisiondependent uncertainty is very scarce and unsuitable for our model. Our method can solve the ASP problem under arbitrarily smooth showup probability functions. We present solutions under different patterns of noshow behavior and demonstrate that breaking the assumption of constant showup probability substantially changes the scheduling solutions. We conduct numerical experiments in a variety of settings to compare our results with those obtained with a distributionally robust optimization method developed in the literature. The cost reduction obtained with our method, which we call the value of distribution information, can be interpreted as how much the system performance can be improved by knowing the distribution of the service times, compared to not knowing it. We observe that the value of distribution information is up to 31% of the baseline cost, and that such value is higher when the system is crowded or/and the waiting time cost is relatively high.
Summary of Contribution: This paper studies an appointment scheduling problem under timedependent patient noshow behavior, a situation commonly observed in practice. The problem belongs to the class of stochastic optimization problems with decisiondependent uncertainties in the operations research literature. Such problems are notoriously difficult to solve as a result of the lack of convexity, and the present case requires different techniques because of the presence of continuous distributions for the service times. A stochastic projected gradient path method, which includes the development of specialized techniques to estimate the gradient of the objective function, is proposed to solve the problem. For problems with a similar structure, the algorithm can be applied once the gradient estimator of the objective function is obtained. Extensive numerical studies are presented to demonstrate the quality of the solutions, the importance of modeling timedependent noshows in appointment scheduling, and the value of using distribution information about the service times. 
Letelier, O. R., Clautiaux, F., & Sadykov, R. (2022). Bin Packing Problem with Time Lags. INFORMS J. Comput., Early Access.
Abstract: We introduce and motivate several variants of the bin packing problem where bins are assigned to time slots, and minimum and maximum lags are required between some pairs of items. We suggest two integer programming formulations for the general problem: a compact one and a stronger formulation with an exponential number of variables and constraints. We propose a branchcutandprice approach that exploits the latter formulation. For this purpose, we devise separation algorithms based on a mathematical characterization of feasible assignments for two important special cases of the problem: when the number of possible bins available at each period is infinite and when this number is limited to one and time lags are nonnegative. Computational experiments are reported for instances inspired from a realcase application of chemical treatment planning in vineyards, as well as for literature instances for special cases of the problem. The experimental results show the efficiency of our branchcutandprice approach, as it outperforms the compact formulation on newly proposed instances and is able to obtain improved lower and upper bounds for literature instances. Summary of Contribution: The paper considers a new variant of the bin packing problem, which is one of the most important problems in operations research. A motivation for introducing this variant is given, as well as a reallife application. We present a novel and original exact branchcutandprice algorithm for the problem. We implement this algorithm, and we present the results of extensive computational experiments. The results show a very good performance of our algorithm. We give several research directions that can be followed by subsequent researchers to extend our contribution to more complex and generic problems.

Letelier, O. R., Espinoza, D., Goycoolea, M., Moreno, E., & Munoz, G. (2020). Production Scheduling for Strategic Open Pit Mine Planning: A MixedInteger Programming Approach. Oper. Res., 68(5), 1425–1444.
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 mixedinteger programming, the number of blocks used to represent realworld 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 benchphase 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 branchandbound algorithm on the problems with larger gaps, we are able to further reduce the average from 1.52% to 0.71%.

Mejia, G., & Pereira, J. (2020). Multiobjective scheduling algorithm for flexible manufacturing systems with Petri nets. J. Manuf. Syst., 54, 272–284.
Abstract: In this work, we focus on general multiobjective 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 reallife 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 (NSGAII) that explicitly addresses the multiobjective nature of the problem and (3) a multiobjective 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.
Keywords: Machine scheduling; Multiobjective optimization; Petri nets

Ogunmodede, O., Lamas, P., Brickey, A., Bogin, G., & Newman, A. (2022). Underground production scheduling with ventilation and refrigeration considerations. Optim. Eng., Early Access.
Abstract: Underground mine production scheduling determines when, if ever, activities associated with the extraction of ore should be executed. The accumulation of heat in the mine where operators are working is a major concern. At the time of this writing, production scheduling and ventilation decisions are not made in concert. Correspondingly, heat limitations are largely ignored. Our mixedinteger program maximizes net present value subject to constraints on precedence, and mill and extraction capacities with the consideration of heat using thermodynamic principles, while affording the option of activating refrigeration to mitigate heat accumulation. In seconds to hours, depending on the problem size (up to thousands of activities and 900 daily time periods), a corresponding methodology that exploits the mathematical problem structure provides schedules that maintain a safe working environment for mine operators; optimality gaps are no more than 15% and average less than half that for otherwiseintractable instances.

OsorioValenzuela, L., Pereira, J., Quezada, F., & Vasquez, O. C. (2019). Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints. Appl. Math. Model., 74, 512–527.
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 branchandprice approach. The results show that the branchandprice 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.

Pereira, J. (2016). The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective. Comput. Oper. Res., 66, 141–152.
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 branchandbound 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 (2540 jobs depending on the characteristics of the instance). (c) 2015 Elsevier Ltd. All rights reserved.
Keywords: Scheduling; Single machine; Uncertainty; Robust optimization; Branchandbound

Pereira, J., & Vasquez, O. C. (2017). The single machine weighted mean squared deviation problem. Eur. J. Oper. Res., 261(2), 515–529.
Abstract: This paper studies a single machine problem related to the justInTime (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 andcut approach to solve a timeindexed 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.
Keywords: Scheduling; Single machine; JIT; Branchandcut; Dominance properties

Reus, L., Belbeze, M., Feddersen, H., & Rubio, E. (2018). Extraction Planning Under Capacity Uncertainty at the Chuquicamata Underground Mine. Interfaces, 48(6), 543–555.
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 stochasticbased solution can achieve the same expected profits as the deterministicbased solution. However, the earnings of the stochasticbased 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 deterministicbased solution, this average increases from 5% to 9%.

Yuraszeck, F., Mejia, G., Pereira, J., & Vila, M. (2022). A Novel Constraint Programming Decomposition Approach for the Total Flow Time Fixed Group Shop Scheduling Problem. Mathematics, 10(3), 329.
Abstract: This work addresses a particular case of the group shop scheduling problem (GSSP) which will be denoted as the fixed group shop scheduling problem (FGSSP). In a FGSSP, job operations are divided into stages and each stage has a set of machines associated to it which are not shared with the other stages. All jobs go through all the stages in a specific order, where the operations of the job at each stage need to be finished before the job advances to the following stage, but operations within a stage can be performed in any order. This setting is common in companies such as leaf spring manufacturers and other automotive companies. To solve the problem, we propose a novel heuristic procedure that combines a decomposition approach with a constraint programming (CP) solver and a restart mechanism both to avoid local optima and to diversify the search. The performance of our approach was tested on instances derived from other scheduling problems that the FGSSP subsumes, considering both the cases with and without anticipatory sequencedependent setup times. The results of the proposed algorithm are compared with offtheshelf CP and mixed integer linear programming (MILP) methods as well as with the lower bounds derived from the study of the problem. The experiments show that the proposed heuristic algorithm outperforms the other methods, specially on largesize instances with improvements of over 10% on average.
Keywords: scheduling; fixed group shop; group shop; constraint programming

Yushimito, W. F., Ban, X. G., & HolguinVeras, J. (2015). Correcting the Market Failure in Work Trips with Work Rescheduling: An Analysis Using Bilevel Models for the Firmworkers Interplay. Netw Spat. Econ., 15(3), 883–915.
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. Bilevel programming models are used to investigate the equilibrium reached from the firmworkers 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.
