Search

We focus on the resource provisioning problem of a cloud consumer from an Infrastructure-as-a-Service type of cloud. The cloud provider offers two deployment options, which can be mixed and matched as appropriate. Cloud instances may be reserved for a fixed time period in advance at a smaller usage cost per hour but require a full commitment and payment for the entire contract duration. In contrast, on-demand instances reflect a pay-as-you-go policy at a premium. The trade-off between these two options is rooted in the inherent uncertainty in demand and price and makes it attractive to complement a base reserved capacity with on-demand capacity to hedge against the spikes in demand. This paper provides several novel multi-stage stochastic programming formulations to enable a cloud consumer to handle the cloud resource provisioning problem at a tactical level. We first formulate the cloud resource provisioning problem as a risk-neutral multi-stage stochastic program, which serves as the base model for further modeling variants. In our second set of models, we also incorporate a certain concept of system reliability. In particular, chance constraints integrated into the base formulation require a minimum service level met from reserved capacity, provide more visibility into the future available capacity, and smooth out expensive on-demand usage by hedging against possible demand fluctuations. An extensive computational study demonstrates the value of the proposed models by discussing computational performance, gleaning practical managerial insights from the analysis of the solutions of the proposed models, and quantifying the value of the stochastic solutions.

Research on non-regular performance measures is at best scarce in the deterministic machine scheduling literature with machine unavailability constraints. Moreover, almost all existing works in this area assume either that processing on jobs interrupted by an interval of machine unavailability may be resumed without any additional setup/processing or that all prior processing is lost. In this work, we intend to partially fill these gaps by studying the problem of scheduling a single machine so as to minimize the total deviation of the job completion times from an unrestrictive common due date when one or several fixed intervals of unavailability are present in the planning horizon. We also put serious effort into investigating models with semi-resumable jobs so that processing on a job interrupted by an interval of machine unavailability may later be resumed at the expense of some extra processing time. The conventional assumptions regarding resumability are also taken into account. Several interesting cases are identified and explored, depending on the resumability scheme and the location of the interval of machine unavailability with respect to the common due date. The focus of analysis is on structural properties and drawing the boundary between polynomially solvable and $$\mathcal {NP}$$ -complete cases. Pseudo-polynomial dynamic programming algorithms are devised for $$\mathcal {NP}$$ -complete variants in the ordinary sense.

The plethora of research on $$\mathcal {NP}$$NP-hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted to the identical parallel machine scheduling environment. In this context, the main contribution of this work is to recognize and prove that a particular preemptive relaxation for the problem of minimizing the total weighted completion time (TWCT) on a set of unrelated parallel machines naturally admits a non-preemptive optimal solution and gives rise to an exact mixed integer linear programming formulation of the problem. Furthermore, we exploit the structural properties of TWCT and attain a very fast and scalable exact Benders decomposition-based algorithm for solving this formulation. Computationally, our approach holds great promise and may even be embedded into iterative algorithms for more complex shop scheduling problems as instances with up to 1000 jobs and 8 machines are solved to optimality within a few seconds.

The job shop scheduling literature has been dominated by a focus on regular objective functions – in particular the makespan – in its half a century long history. The last twenty years have encountered a spike of interest in other objectives, such as the total weighted tardiness, but research on non-regular objective functions has always been isolated and scattered. Motivated by this observation, we present a tabu search heuristic for a large class of job shop scheduling problems, where the objective is non-regular in general and minimizes a sum of separable convex cost functions attached to the operation start times and the differences between the start times of arbitrary pairs of operations. This problem definition generalizes a number of problems considered earlier in the literature. A particular notion of “critical paths” derived from the so-called timing problem is at the core of the proposed neighborhood definition exploited successfully in a tabu search algorithm. The computational results attest to the promise of our work.

In a recent work, Muter et al. (2013a) identified and characterized a general class of linear programming (LP) problems -- known as problems with column-dependent-rows (CDR-problems). These LPs feature two sets of constraints with mutually exclusive groups of variables in addition to a set of structural linking constraints, in which variables from both groups appear together. In a typical CDR-problem, the number of linking constraints grows very quickly with the number of variables, which motivates generating both columns and their associated linking constraints simultaneously on-the-fly as a general solution strategy. In this paper, we expose the decomposable structure of CDR-problems -- which went unexploited in our earlier work -- via Benders decomposition. However, this approach brings on its own set of theoretical challenges. One group of variables is generated in the Benders master problem, while the generation of the linking constraints is relegated to the Benders subproblem along with the second group of variables. A fallout of this separation is that only a partial description of the dual of the Benders subproblem is available over the course of the algorithm. We demonstrate how the pricing subproblem for the column generation applied to the Benders master problem does also update the dual polyhedron and the existing Benders cuts in the master problem to ensure convergence. Ultimately, a novel integration of delayed Benders cut generation and the simultaneous generation of columns and structural constraints yields a brand-new algorithm for solving large-scale CDR-problems. We illustrate the application of the proposed method on a time-constrained routing problem. Our numerical experiments confirm that the new decomposition method outperforms not only the off-the-shelf solvers but also our previous algorithm for CDR-problems presented in Muter et al. (2013a).

We focus on optimization models involving individual chance constraints, in which only the right-hand side vector is random with a finite distribution. A recently introduced class of such models treats the reliability levels / risk tolerances associated with the chance constraints as decision variables and trades off the actual cost / return against the cost of the selected reliability levels in the objective function. Leveraging recent methodological advances for modeling and solving chance-constrained linear programs with fixed reliability levels, we develop strong mixed-integer programming formulations for this new variant with variable reliability levels. In addition, we introduce an alternate cost function type associated with the risk tolerances which requires capturing the value-at-risk (VaR) associated with a variable reliability level. We accomplish this task via a new integer linear programming representation of VaR. Our computational study illustrates the effectiveness of our mathematical programming formulations. We also apply the proposed modeling approach to a new stochastic last mile relief network design problem and provide numerical results for a case study based on the real-world data from the 2011 Van earthquake in Turkey. (C) 2018 Elsevier Ltd. All rights reserved.

We study an approximation algorithm with a performance guarantee to solve a new $$\mathcal {NP}$$ -hard optimization problem on planar graphs. The problem, which is referred to as the minimum hub cover problem, has recently been introduced to the literature to improve query processing over large graph databases. Planar graphs also arise in various graph query processing applications, such as; biometric identification, image classification, object recognition, and so on. Our algorithm is based on a well-known graph decomposition technique that partitions the graph into a set of outerplanar graphs and provides an approximate solution with a proven performance ratio. We conduct a comprehensive computational experiment to investigate the empirical performance of the algorithm. Computational results demonstrate that the empirical performance of the algorithm surpasses its guaranteed performance. We also apply the same decomposition approach to develop a decomposition-based heuristic, which is much more efficient than the approximation algorithm in terms of computation time. Computational results also indicate that the efficacy of the decomposition-based heuristic in terms of solution quality is comparable to that of the approximation algorithm.

In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many to be included in the formulation directly, or the full set of linking constraints can only be identified, if all variables are generated explicitly. Due to this dependence between columns and rows, we refer to this class of linear programs as problems with column-dependent-rows. To solve these problems, we need to be able to generate both columns and rows on-the-fly within an efficient solution approach. We emphasize that the generated rows are structural constraints and distinguish our work from the branch-and-cut-and-price framework. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm. These assumptions are general enough and cover all problems with column-dependent-rows studied in the literature up until now to the best of our knowledge. We then introduce in detail a set of pricing subproblems, which are used within the proposed column-and-row generation algorithm. This is followed by a formal discussion on the optimality of the algorithm. To illustrate the proposed approach, the paper is concluded by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering problems.

We present a decomposition heuristic for a large class of job shop scheduling problems. This heuristic utilizes information from the linear programming formulation of the associated optimal timing problem to solve subproblems, can be used for any objective function whose associated optimal timing problem can be expressed as a linear program (LP), and is particularly effective for objectives that include a component that is a function of individual operation completion times. Using the proposed heuristic framework, we address job shop scheduling problems with a variety of objectives where intermediate holding costs need to be explicitly considered. In computational testing, we demonstrate the performance of our proposed solution approach.

We consider a single machine earliness/tardiness scheduling problem with general weights, ready times and due dates. Our solution approach is based on a time-indexed preemptive relaxation of the problem. For the objective function of this relaxation, we characterize cost coefficients that are the best among those with a piecewise linear structure with two segments. From the solution to the relaxation with these best objective function coefficients, we generate feasible solutions for the original non-preemptive problem. We report extensive computational results demonstrating the speed and effectiveness of this approach.

In many classes of monitoring applications employing battery-limited sensor networks, periodic sampling of an area with a given precision level is required. For such applications, we provide mathematical programming formulations for deriving the optimal trade-off curve between network lifetime and data precision, and design a practical heuristic for near-optimal operation. The properties of our models and the effectiveness of our heuristic are demonstrated by computational experiments.

We analyze an economic order quantity cost model with unit out-of-pocket holding costs, unit opportunity costs of holding, fixed ordering costs, and general purchase-transportation costs. We identify the set of purchasetransportation cost functions for which this model is easy to solve and related to solving a one-dimensional convex minimization problem. For the remaining purchase-transportation cost functions, when this problem becomes a global optimization problem, we propose a Lipschitz optimization procedure. In particular, we give an easy procedure which determines an upper bound on the optimal cycle length. Then, using this bound, we apply a well-known technique from global optimization. Also for the class of transportation functions related to full truckload (FTL) and less-than-truckload (LTL) shipments and the well-known carload discount schedule, we specialize these results and give fast and easy algorithms to calculate the optimal lot size and the corresponding optimal order-up-to-level. On EOQ Cost Models with Arbitrary Purchase and Transportation Costs (PDF Download Available). Available from: https://www.researchgate.net/publication/265601733_On_EOQ_Cost_Models_with_Arbitrary_Purchase_and_Transportation_Costs [accessed Mar 4, 2016].

We consider the problem of scheduling customer orders in a flow shop with the objective of minimizing the sum of tardiness, earliness (finished goods inventory holding) and intermediate (work-in-process) inventory holding costs. We formulate this problem as an integer program, and based on approximate solutions to two di erent, but closely related, Dantzig-Wolfe reformulations, we develop heuristics to minimize the total cost. We exploit the duality between Dantzig-Wolfe reformulation and Lagrangian relaxation to enhance our heuristics. This combined approach enables us to develop two di erent lower bounds on the optimal integer solution, together with intuitive approaches for obtaining near-optimal feasible integer solutions. To the best of our knowledge, this is the first paper that applies column generation to a scheduling problem with di erent types of strongly NP-hard pricing problems which are solved heuristically. The computational study demonstrates that our algorithms have a significant speed advantage over alternate methods, yield good lower bounds, and generate near-optimal feasible integer solutions for problem instances with many machines and a realistically large number of jobs.

The vast majority of the machine scheduling literature focuses on deterministic problems in which all data is known with certainty a priori. In practice, this assumption implies that the random parameters in the problem are represented by their point estimates in the scheduling model. The resulting schedules may perform well if the variability in the problem parameters is low. However, as variability increases accounting for this randomness explicitly in the model becomes crucial in order to counteract the ill effects of the variability on the system performance. In this paper, we consider single-machine scheduling problems in the presence of uncertain parameters. We impose a probabilistic constraint on the random performance measure of interest, such as the total weighted completion time or the total weighted tardiness, and introduce a generic risk-averse stochastic programming model. In particular, the objective of the proposed model is to find a non-preemptive static job processing sequence that minimizes the value-at-risk (VaR) of the random performance measure at a specified confidence level. We propose a Lagrangian relaxation-based scenario decomposition method to obtain lower bounds on the optimal VaR and provide a stabilized cut generation algorithm to solve the Lagrangian dual problem. Furthermore, we identify promising schedules for the original problem by a simple primal heuristic. An extensive computational study on two selected performance measures is presented to demonstrate the value of the proposed model and the effectiveness of our solution method.

This paper investigates the role of dual information on the performances of heuristics designed for solving the set covering problem. After solving the linear programming relaxation of the problem, the dual information is used to obtain the two main approaches proposed here: (i) The size of the original problem is reduced and then the resulting model is solved with exact methods. We demonstrate the effectiveness of this approach on a rich set of benchmark instances compiled from the literature. We conclude that set covering problems of various characteristics and sizes may reliably be solved to near optimality without resorting to custom solution methods. (ii) The dual information is embedded into an existing heuristic. This approach is demonstrated on a well-known local search based heuristic that was reported to obtain successful results on the set covering problem. Our results demonstrate that the use of dual information significantly improves the efficacy of the heuristic in terms of both solution time and accuracy.

Research on due date-oriented objectives in the parallel machine environment is at best scarce compared to objectives such as minimizing the makespan or the completion time-related performance measures. Moreover, almost all existing work in this area is focused on the identical parallel machine environment. In this study, we leverage on our previous work on the single machine total weighted tardiness (TWT) and total weighted earliness/tardiness (TWET) problems and develop a new preemptive relaxation for both problems on a bank of unrelated parallel machines. The key contribution of this paper is devising a computationally effective Benders decomposition algorithm to solve the preemptive relaxation formulated as a mixed-integer linear program. The optimal solution of the preemptive relaxation provides a tight lower bound. Moreover, it offers a near-optimal partition of the jobs to the machines. We then exploit recent advances in solving the nonpreemptive single-machine TWT and TWET problems for constructing nonpreemptive solutions of high quality to the original problem. We demonstrate the effectiveness of our approach with instances of up to five machines and 200 jobs.

In this study, we solve a robust version of the airline crew pairing problem. Our concept of robustness was partially shaped during our discussions with small local airlines in Turkey which may have to add a set of extra flights into their schedule at short notice during operation. Thus, robustness in this case is related to the ability of accommodating these extra flights at the time of operation by disrupting the original plans as minimally as possible. We focus on the crew pairing aspect of robustness and prescribe that the planned crew pairings incorporate a number of predefined recovery solutions for each potential extra flight. These solutions are implemented only if necessary for recovery purposes and involve either inserting an extra flight into an existing pairing or partially swapping the flights in two existing pairings in order to cover an extra flight. The resulting mathematical programming model follows the conventional set covering formulation of the airline crew pairing problem typically solved by column generation with an additional complication. The model includes constraints that depend on the columns due to the robustness consideration and grows not only column-wise but also row-wise as new columns are generated. To solve this difficult model, we propose a row and column generation approach. This approach requires a set of modifications to the multi-label shortest path problem for pricing out new columns (pairings) and various mechanisms to handle the simultaneous increase in the number of rows and columns in the restricted master problem during column generation. We conduct computational experiments on a set of real instances compiled from local airlines in Turkey. © 2010 Elsevier Ltd. 106M472 Türkiye Bilimsel ve Teknolojik AraÅ?tirma Kurumu This research has been supported by The Scientific and Technological Research Council of Turkey (TÜBİTAK) under Grant 106M472 .

In this study, a conceptual framework is given for the dynamic resource-constrained multi-project scheduling problem with weighted earliness/tardiness costs (DRCMPSPWET), and a mathematical programming formulation of the problem is provided. In DRCMPSPWET, a project arrives on top of an existing project portfolio, and a due date has to be quoted for the new project while minimizing the costs of schedule changes. The objective function consists of the weighted earliness/tardiness costs of the activities of the existing projects in the current baseline schedule plus a term that increases linearly with the anticipated completion time of the new project. An iterated local search (LS)-based approach is developed for large instances of this problem. In order to analyze the performance and behavior of the proposed method, a new multi-project data set is created by controlling the total number of activities, the due date tightness, the due date range, the number of resource types, and the completion time factor in an instance. A series of computational experiments are carried out to test the performance of the LS approach. Exact solutions are provided for small instances. The results indicate that the LS heuristic performs well in terms of both solution quality and solution time.

The crew pairing problem is an airline optimization problem where a set of least costly pairings (consecutive flights to be flown by a single crew) that covers every flight in a given flight network is sought. A pairing is defined by using a very complex set of feasibility rules imposed by international and national regulatory agencies, and also by the airline itself. The cost of a pairing is also defined by using complicated rules. When an optimization engine generates a sequence of flights from a given flight network, it has to check all these feasibility rules to ensure whether the sequence forms a valid pairing. Likewise, the engine needs to calculate the cost of the pairing by using certain rules. However, the rules used for checking the feasibility and calculating the costs are usually not static. Furthermore, the airline companies carry out what-if-type analyses through testing several alternate scenarios in each planning period. Therefore, embedding the implementation of feasibility checking and cost calculation rules into the source code of the optimization engine is not a practical approach. In this work, a high level language called ARUS is introduced for describing the feasibility and cost calculation rules. A compiler for ARUS is also implemented in this work to generate a dynamic link library to be used by crew pairing optimization engines.

Avella et al. (2006) [Avella, P., D'Auria, B., Salerno, S. (2006). A LP-based heuristic for a time-constrained routing problem. European Journal of Operational Research 173:120-124] investigate a time-constrained routing (TCR) problem. The core of the proposed solution approach is a large-scale linear program (LP) that grows both row- and column-wise when new variables are introduced. Thus, a column-and-row generation algorithm is proposed to solve this LP optimally, and an optimality condition is presented to terminate the column-and-row generation algorithm. We demonstrate that this optimality condition is incorrect and may lead to a suboptimal solution at termination. We identify the source of this error and discuss how the generic column-and-row generation algorithm proposed by Muter et al. (2010) may be applied to this TCR problem in order to solve the proposed large-scale LP correctly.

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck - tabu search (SB-TS) algorithm by replacing the reoptimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.

In this article, we investigate two different distributed algorithms for constructing a minimum power broadcast tree with a maximum depth ? which corresponds to the maximum tolerable end-to-end delay in the network. Distributed Tree Expansion (DTE) is based on an implementation of a distributed minimum spanning tree algorithm in which the tree grows at each iteration by adding a node that can cover the maximum number of currently uncovered nodes in the network with minimum incremental transmission power and without violating the delay constraint. In Distributed Link Substitution (DLS), given a feasible broadcast tree, the solution is improved by replacing expensive transmissions by transmissions at lower power levels while reserving the feasibility of the tree with respect to the delay bound. Although DTE increases the message complexity to O(n3) from O(n2?) in a network of size n, it provides up to 50% improvement in total expended power compared to DLS.

In many network applications, broadcasting is an important part of the operation where data generated by a source is disseminated to all users in the network. Judicious use of limited energy resources in wireless networks typically requires routing packets along the branches of a tree spanning the source and the destination nodes. In addition, networks that support real-time traffic are also required to provide certain quality of service (QoS) guarantees in terms of the end-to-end delay along the individual paths from the source to each of the destination nodes. Therefore, in this paper we focus on constructing a minimum power broadcast tree with a maximum depth D which corresponds to the maximum tolerable end-to-end delay in the network. We investigate two different distributed algorithms for this purpose: Distributed Tree Expansion (DTE) and Distributed Link Substitution (DLS). DTE is based on an implementation of a distributed minimum spanning tree algorithm in which the tree grows at each iteration by adding a node that can cover the maximum number of currently uncovered nodes in the network with minimum incremental transmission power and without violating the delay constraint. In DLS, we begin with a feasible broadcast tree, and then improve that solution by replacing expensive transmissions by transmissions at lower power levels while preserving the feasibility of the tree with respect to the delay bound. Hence, DTE is constructive in nature while DLS is an improvement algorithm. Although DTE increases the message complexity to O(n^3) from O(n^2) in a network of size n, it provides up to 50% improvement in total expended power compared to DLS.

This paper discusses a modeling approach to robust crew pairing when a set of extra flights is likely to be added to the regular flight schedule. The set of these possible extra flights is known at the planning stage. We demonstrate that these extra flights may be incorporated into the schedule if necessary by modifying the planned crew pairings appropriately and without delaying or canceling existing flights. To this end, we either identify a pair of crews whose schedules may be (partially) swapped while adding an extra flight into the schedule or show that an extra flight may be inserted into the schedule of a crew without affecting others. We note that deadheading may be necessary in either case. For these two types of solutions, we define the appropriate feasibility rules with respect to the common airline regulations. We then propose two robust mathematical programming models that consider incorporating such solutions into the set of selected pairings while keeping the increase in the crew cost at an acceptable level. The baseline solution for comparison is found by a conventional crew pairing model in the literature which ignores robustness at the planning stage and relies on recovery procedures at the time of operation. We also propose the variations of the two models, where the double counting of the possible solutions across extra flights is prevented. Finally, we conduct computational experiments on a set of data generated from the actual data of an airline company. We solve the crew pairing problem both with the proposed robust models and the conventional model. Our results demonstrate the benefits of the proposed modeling approach and indicate that the proposed robust models provide natural options to recovery without disrupting the existing flights at a relatively small incremental cost, which is visible at the planning stage. (C) 2008 Elsevier Ltd. All rights reserved.

We consider source-initiated broadcast session traffic in an ad hoc wireless network operating under a hard constraint on the end-to-end delay between the source and any node in the network. Our objective in this paper is to construct an energy-efficient broadcast tree that has a maximum depth Delta, where Delta represents the end-to-end delay constraint in the network. We first characterize the optimal solution to a closely related problem in dense networks using a dynamic programming formulation. The solution to the dynamic program indicates that there is a single optimal policy applicable to all dense networks. Elaborating on the insights provided by the structure of the problem in dense networks, we design an algorithm for finding a solution to the delay constrained minimum power broadcasting problem in sparse networks.

The problem of maximizing network lifetime in wireless ad-hoc networks is addressed with a cooperative routing approach. The network lifetime optimization problem is defined as a linear programming problem and it is shown with simulations that networks utilizing cooperative transmission have larger lifetime than the networks not utilizing.