First-order inertial algorithms involving dry friction damping

We present a Branch-and-Cut algorithm for a class of nonlinear chance-constrained mathematical optimization problems with a finite number of scenarios. Unsatisfied scenarios can enter a recovery mode. This class corresponds to problems that can be reformulated as deterministic convex mixed-integer nonlinear programming problems with indicator variables and continuous scenario variables, but the size of the reformulation is large and quickly becomes impractical as the number of scenarios grows. The Branch-and-Cut algorithm is based on an implicit Benders decomposition scheme, where we generate cutting planes as outer approximation cuts from the projection of the feasible region on suitable subspaces. The size of the master problem in our scheme is much smaller than the deterministic reformulation of the chance-constrained problem. We apply the Branch-and-Cut algorithm to the mid-term hydro scheduling problem, for which we propose a chance-constrained formulation. A computational study using data from ten hydroplants in Greece shows that the proposed methodology solves instances faster than applying a general-purpose solver for convex mixed-integer nonlinear programming problems to the deterministic reformulation, and scales much better with the number of scenarios.

     

A (0–1) goal programming model for scheduling the tour of a marketing executive

This paper addresses the problem of scheduling the tour of a marketing executive (ME) of a large electronics manufacturing company in India. In this problem, the ME has to visit a number of customers in a given planning period. The scheduling problem taken up in this study is different from the various personnel scheduling problems addressed in the literature. This type of personnel scheduling problem can be observed in many other situations such as periodical visits of inspection officers, tour of politicians during election campaigns, tour of mobile courts, schedule of mobile stalls in various areas, etc. In this paper the tour scheduling problem of the ME is modeled using (0–1) goal programming (GP). The (0–1) GP model for the data provided by the company for 1 month has 802 constraints and 1167 binary variables. The model is solved using LINDO software package. The model takes less than a minute (on a 1.50 MHz Pentium machine with 128 MB RAM) to get a solution of the non-preemptive version and about 6 days for the preemptive version. The main contribution is in problem definition and development of the mathematical model for scheduling the tour.     

Forestry management under uncertainty

The forest harvest and road construction planning problem consists fundamentally of managing land designated for timber production and divided into harvest cells. For each time period the planner must decide which cells to cut and what access roads to build in order to maximize expected net profit. We have previously developed deterministic mixed integer linear programming models for this problem. The main contribution of the present work is the introduction of a multistage Stochastic Integer Programming model. This enables the planner to make more robust decisions based on a range of timber price scenarios over time, maximizing the expected value instead of merely analyzing a single average scenario. We use a specialization of the Branch-and-Fix Coordination algorithmic approach. Different price and associated probability scenarios are considered, allowing us to compare expected profits when uncertainties are taken into account and when only average prices are used. The stochastic approach as formulated in this work generates solutions that were always feasible and better than the average solution, while the latter in many scenarios proved to be infeasible.     

A robust data envelopment analysis model with different scenarios

Input and output data, under uncertainty, must be taken into account as an essential part of data envelopment analysis (DEA) models in practice. Many researchers have dealt with this kind of problem using fuzzy approaches, DEA models with interval data or probabilistic models. This paper presents an approach to scenario-based robust optimization for conventional DEA models. To consider the uncertainty in DEA models, different scenarios are formulated with a specified probability for input and output data instead of using point estimates. The robust DEA model proposed is aimed at ranking decision-making units (DMUs) based on their sensitivity analysis within the given set of scenarios, considering both feasibility and optimality factors in the objective function. The model is based on the technique proposed by Mulvey et al. (1995) for solving stochastic optimization problems. The effect of DMUs on the product possibility set is calculated using the Monte Carlo method in order to extract weights for feasibility and optimality factors in the goal programming model. The approach proposed is illustrated and verified by a case study of an engineering company.     

Scheduling projects with heterogeneous resources to meet time and quality objectives

In service organizations, heterogeneity in workforce skills can lead to variation in end-product/service quality. The multi-mode, resource-constrained, project scheduling problem (MRCPSP), which assumes similar skills among resources in a given resource pool, accounts for differences in quality levels of individuals by assigning different activity durations depending on the skill level used. This approach is often inadequate to model the problem type investigated here. Using typical projects from the customer training division of a large telecommunications company (which motivated this research), a labor assignment problem using a successive work–time concept is formulated and solved using integer programming optimization procedures. The setting represents a multiple-project environment where projects are separate and independent, but require the same renewable resource mix for their completion. The paper demonstrates how the output of the model can be used to identify bottlenecks (or critical resource skills), and also demonstrates how cross-training the appropriately skilled groups or individuals can increase throughput. The approach guides decision-making concerning which workers to cross-train in order to extract the greatest benefits from worker-flexibility.     

Two-phase optimization of coal strategies at a power station

Development of optimal coal mining and stockpiling strategies for a new 960 MW thermal power station depends strongly on the operation of New Zealand's mixed hydro/thermal power system. To overcome the large dimensionality of the problem the optimization proceeds in two phases for each future scenario studied. Phase 1 finds optimal hydro operating strategies with thermal generation in merit order of marginal fuel costs. It uses stochastic dynamic programming. The hydro generating strategies are used as input to the phase 2 stochastic simulation of the coal mining and stockpiling operation at the new thermal station. Finally, a strategy is identified which is a priori best over all future scenarios of industrial development and oil prices studied.     

Interior point method for long-term generation scheduling of large-scale hydrothermal systems

This paper presents an interior point method for the long-term generation scheduling of large-scale hydrothermal systems. The problem is formulated as a nonlinear programming one due to the nonlinear representation of hydropower production and thermal fuel cost functions. Sparsity exploitation techniques and an heuristic procedure for computing the interior point method search directions have been developed. Numerical tests in case studies with systems of different dimensions and inflow scenarios have been carried out in order to evaluate the proposed method. Three systems were tested, with the largest being the Brazilian hydropower system with 74 hydro plants distributed in several cascades. Results show that the proposed method is an efficient and robust tool for solving the long-term generation scheduling problem.     

Optimizing inventory decisions in a two-level supply chain with order quantity constraints

A fundamental assumption in traditional inventory models is that all of the ordered items are of perfect quality. A two-level supply chain is considered consists of one retailer and a collection of suppliers that operate within a finite planning horizon, including multiple periods, and a model is formulated that simultaneously determines both supplier selection and inventory allocation problems in the supply chain. It is supposed that the ordered products dependent on the suppliers include a certain percentage of imperfect quality products and have different prices. In this paper, we study the impact of the retailer’s financial constraint. On the other hand, suppliers have restricted capacities and set minimum order quantity (MOQ) policy for the retailer’s order amount happened in each period. So, the problem is modeled as a mixed integer nonlinear programming. The purpose of this model is to maximize the total profit. The nutrients, fishery and fruitage industries give good examples for the proposed model. A numerical example is presented to indicate the efficiency of the proposed model. Considering the complexity of the model, a genetic algorithm (GA) is presented to solve the model. We demonstrate analytically that the proposed genetic algorithm is suitable in the feasible situations.     

A column generation algorithm for the estimation of origin–destination matrices in congested traffic networks

The general problem of estimating origin–destination (O–D) matrices in congested traffic networks is formulated as a mathematical programme with equilibrium constraints, referred to as the demand adjustment problem (DAP). This approach integrates the O–D matrix estimation and the network equilibrium assignment into one process. In this paper, a column generation algorithm for the DAP is presented. This algorithm iteratively solves a deterministic user equilibrium model for a given O–D matrix and a DAP restricted to the previously generated paths, whose solution generates a new O–D trip matrix estimation. The restricted DAP is formulated via a single level optimization problem. The convergence on local minimum of the proposed algorithm requires only the continuity of the link travel cost functions and the gauges used in the definition of the DAP.     

A tabu search tutorial based on a real-world scheduling problem

We apply a tabu search method to a scheduling problem of a company producing cables for cars: the task is to determine on what machines and in which order the cable jobs should be produced in order to save production costs. First, the problem is modeled as a combinatorial optimization problem. We then employ a tabu search algorithm as an approach to solve the specific problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate how these different implementations improve the results. Moreover, we show how the computational cost in each iteration of the algorithm can be reduced drastically from O(n ³) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders).     

Unit commitment in power generation – a basic model and some extensions

For the unit commitment problem in the hydro-thermal power system of VEAG Vereinigte Energiewerke AG Berlin we present a basic model and discuss possible extensions where both primal and dual solution approaches lead to flexible optimization tools. Extensions include staggered fuel prices, reserve policies involving hydro units, nonlinear start-up costs, and uncertain load profiles. This revised version was published online in June 2006 with corrections to the Cover Date.     

An exact branch-and-price algorithm for scheduling rescue units during disaster response

In disaster operations management, a challenging task for rescue organizations occurs when they have to assign and schedule their rescue units to emerging incidents under time pressure in order to reduce the overall resulting harm. Of particular importance in practical scenarios is the need to consider collaboration of rescue units. This task has hardly been addressed in the literature. We contribute to both modeling and solving this problem by (1) conceptualizing the situation as a type of scheduling problem, (2) modeling it as a binary linear minimization problem, (3) suggesting a branch-and-price algorithm, which can serve as both an exact and heuristic solution procedure, and (4) conducting computational experiments – including a sensitivity analysis of the effects of exogenous model parameters on execution times and objective value improvements over a heuristic suggested in the literature – for different practical disaster scenarios. The results of our computational experiments show that most problem instances of practically feasible size can be solved to optimality within ten minutes. Furthermore, even when our algorithm is terminated once the first feasible solution has been found, this solution is in almost all cases competitive to the optimal solution and substantially better than the solution obtained by the best known algorithm from the literature. This performance of our branch-and-price algorithm enables rescue organizations to apply our procedure in practice, even when the time for decision making is limited to a few minutes. By addressing a very general type of scheduling problem, our approach applies to various scheduling situations.     

A Mixed Integer Linear Programming model for simultaneous design and scheduling of flowshop plants

Models representing batch plants, especially flowshop facilities where all the products require the same processing sequence, have received much attention in the last decades. In particular, plant design and production scheduling have been addressed as disconnected problems due to the tremendous combinatory complexity associated to their simultaneous optimization. This paper develops a model for both design and scheduling of flowshop batch plants considering mixed product campaign and parallel unit duplication. Thus, a realistic formulation is attained, where industrial and commercial aspects are jointly taken into account. The proposed approach is formulated as a Mixed Integer Linear Programming model that determines the number of units per stages, unit and batch sizes and batch sequencing in each unit in order to fulfill the demand requirements at minimum investment cost. A set of novel constraints is proposed where the number of batches of each product in the campaign is an optimization variable. The approach performance is evaluated through several numerical examples.     

Shipment planning at oil refineries using column generation and valid inequalities

In this paper we suggest an optimization model and a solution method for a shipment planning problem. This problem concerns the simultaneous planning of how to route a fleet of ships and the planning of which products to transport in these ships. The ships are used for moving products from oil refineries to storage depots. There are inventory levels to consider both at the refineries and at the depots. The inventory levels are affected by the process scheduling at the refineries and demand at the depots. The problem is formulated using an optimization model including an aggregated representation of the process scheduling at the refineries. Hence, we integrate the shipment planning and the process scheduling at the refineries. We suggest a solution method based on column generation, valid inequalities, and constraint branching. The solution method is tested on data provided by the Nynas oil refinery company and solutions are obtained within 4 hours, for problem instances of up to 3 refineries, 15 depots, and 4 products when considering a time horizon of 42 days.     

A priority-rule method for project scheduling with work-content constraints

The activities of a project are in general characterized by a work content in terms of resource–time units, e.g. person-days. Even though most project scheduling models assume a time-invariant resource usage, normally it is possible to vary the resource usage during the execution of an activity. Typically, a lower and an upper bound on this resource usage and a minimum time lag between consecutive changes of this resource usage are prescribed. The project scheduling problem studied in this paper consists in determining a feasible resource-usage profile for each activity such that the project duration is minimized subject to precedence and resource-capacity constraints. While the known solution methods interpret the prescribed work content as a lower bound, we assume that each activity’s work content must be processed exactly.     

SOCRATES: A system for scheduling hydroelectric generation under uncertainty

The Pacific Gas and Electric Company, the largest investor-owned energy utility in the United States, obtains a significant fraction of its electric energy and capacity from hydrogeneration. Although hydro provides valuable flexibility, it is subject to usage limits and must be carefully scheduled. In addition, the amount of energy available from hydro varies widely from year to year, depending on precipitation and streamflows. Optimal scheduling of hydrogeneration, in coordination with other energy sources, is a stochastic problem of practical significance to PG&E. SOCRATES is a system for the optimal scheduling of PG&E's various energy sources over a one- to two-year horizon. This paper concentrates on the component of SOCRATES that schedules hydro. The core is a stochastic optimization model, solved using Benders decomposition. Additional components are streamflow forecasting models and a database containing hydrological information. The stochastic hydro scheduling module of SOCRATES is undergoing testing in the user's environment, and we expect PG&E hydrologists and hydro schedulers to place progressively more reliance upon it.     

On the two-phase method for preemptive scheduling

Preemptive scheduling problems on parallel processors may in some cases be solved by a two-phase method: forst solve a LP problem which will give the minimum total completion time T and the processing times of the jobs on the various processors; second construct a feasible schedule using T time units. Some extensions of this procedure are discussed. A general model for preemptive scheduling is described with a two-phase method for solving problems of this type.     

Real time management of a metro rail terminus

This paper addresses a scheduling problem arising in the real time management of a metro rail terminus. It mainly consists in routing incoming trains through the station and scheduling their departures with the objective of optimizing punctuality and regularity of train service. The purpose of this work is to develop an automated train traffic control system, able to directly implement most traffic control actions, without the authorization of the local area manager. The scheduling problem is modeled as a bicriteria job shop scheduling problem with additional constraints. The two objective functions, in lexicographical order, are the minimization of tardiness/earliness and the headway optimization. The problem is solved in two steps. At first a heuristic builds a feasible solution by considering the first objective function. Then the regularity is optimized without deteriorating the first objective function. Computational results show that the system is able to manage the terminus very efficiently.     

Min–max and min–max (relative) regret approaches to representatives selection problem

The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min?Cmax and min?Cmax (relative) regret approaches are used for making a selection decision. The arising min?Cmax, min?Cmax regret and min?Cmax relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line.     

A biased random-key genetic algorithm for the project scheduling problem with flexible resources

In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an \(\mathcal {NP}\)-hard combinatorial optimization problem that consists of scheduling a set of activities requiring specific resource units of several skills. The goal is to minimize the makespan of the project. We propose a biased random-key genetic algorithm for computing feasible solutions for the referred problem. We study different decoding mechanisms: an already existing method in the literature, a new adapted serial scheduling generation scheme, and a combination of both. The new procedure is tested using a set of benchmark instances of the problem. The results provide strong evidence that the new heuristic is robust and yields high-quality feasible solutions.