This paper presents algorithms for single and parallel identical machine scheduling problems. While the overall algorithm can be viewed as a branch-cut-and-price over a very large extended formulation, a number of auxiliary techniques are necessary to make the column generation effective. Those techniques include a powerful fixing by reduced costs and a new proposed dual … Read more
We investigate the problem of simultaneously determining the location of facilities and the design of vehicle routes to serve customer demands under vehicle and facility capacity restrictions. We present a set-partitioning-based formulation of the problem and study the relationship between his formulation and the graph-based formulations that have been used in previous studies of this … Read more
This paper addresses the one machine scheduling problem in which $n$ jobs have distinct due dates with earliness and tardiness costs. Fast neighborhoods are proposed for the problem. They are based on a block representation of the schedule and can be computed in $O(n^2)$. A timing operator is presented as well as swap and extract-and-reinsert … Read more
In this paper I investigate several offline and online data transfer scheduling problems and propose efficient algorithms and techniques for addressing them. In the offline case, I present a novel, heuristic, algorithm for scheduling files with divisible sizes on multiple disjoint paths, in order to maximize the total profit (the problem is equivalent to the … Read more
The problem of routing and wavelength assignment (RWA) in wavelength division multiplexing (WDM) optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned different wavelengths. This problem was shown to be NP-hard when the objective is to … Read more
The main goal of this paper is to develop a numerical procedure for construction of covariance matrices such that for a given covariance structural model and a discrepancy function the corresponding minimizer of the discrepancy function has a specified value. Often construction of such matrices is a first step in Monte Carlo studies of statistical … Read more
This article presents techniques for constructing robust Branch-Cutand-Price algorithms on a number of Vehicle Routing Problem variants. The word “robust” stress the effort of controlling the worst-case complexity of the pricing subproblem, keeping it pseudo-polynomial. Besides summarizing older research on the topic, some promising new lines of investigation are also presented, specially the development of … Read more
This paper presents a robust branch-cut-and-price algorithm for the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), vehicles may have distinct capacities and costs. The columns in the formulation are associated to q-routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudo-polynomial time. Powerful new families of cuts are also proposed, which … Read more
Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes … Read more
The ballroom dancing showcases at Fred Astaire East Side Dance Studio in Manhattan are held at least twice a year and provide the students with an environment for socializing, practice, and improvement. The most important part of a showcase organization is the construction of the dance presentations timetable, and, with the number of participants increasing … Read more