Stochastically minimizing total flowtime in flowshops with no waiting space

The problem of scheduling n jobs in a two-machine flowshop with constant and known processing times is considered with the total flowtime performance measure. The machines are subject to random breakdowns and there is no waiting space between them. The problem is formulated and an expression for the completion time of the jobs is obtained in terms of the processing times and the breakdown elements. Provided that the counting processes associated with both machines have stationary increments property, a sequence that stochastically minimizes the performance criterion is established for the cases when only the first or the second machine suffers breakdowns.     

Boundary regularity for minimizing currents with prescribed mean curvature

We prove complete boundary regularity for energy minimizing integer multiplicity rectifiablen currents in ⁿ⁺¹ of prescribed mean curvatureH with boundaryB= represented by an oriented smooth submanifold of dimensionn – 1 in sun+1. We also give applications to the Plateau problem for surfaces with prescribed mean curvature.This article was processed by the author using the LaT_EX style filepljour1 from Springer-Verlag.     

MULTIQ: A Queueing Model for FMSs with Several Pallet Types

Analytical modelling of the work flow through flexible manufacturing systems (FMSs), based on closed queueing network models, has been successfully applied to the early stages of design and analysis of FMSs. This paper describes the advantages of using multiple job-class closed queueing networks for modelling realistic situations occurring in FMSs. The general modelling of FMSs by closed queueing networks is first reviewed. The way Solberg's CAN-Q—a single job-class queueing-based package—deals with several part types is clarified. A new model called MULTIQ, allowing multiple pallet types, each of which is used by several part types, is proposed. Results are derived using the data from an existing FMS. The use of the MULTIQ model for optimization purposes is suggested by some examples.     

Generalized minimizing movements for the mean curvature flow with Dirichlet boundary condition

We study a variational approach, called Generalized Minimizing Movemenents (GMM) and proposed by E. De Giorgi, to evolution of hypersurfaces by mean curvature in the case of a Dirichlet boundary datum. We prove an existence theorem of a GMM when on the initial solid are made suitable geometric hypotheses.

---

Sunto Si studia un approccio variazionale, detto Movimenti Minimizzanti Generalizzati (GMM) e proposto da Ennio De Giorgi, per l’evoluzione di una ipersuperficie secondo la curvatura media con un dato al bordo di tipo Dirichlet. Viene provato un teorema di esistenza quando sul solido iniziale siano fatte opportune ipotesi di tipo geometrico.

     

Mathematical models for job-shop scheduling problems with routing and process plan flexibility

As a result of rapid developments in production technologies in recent years, flexible job-shop scheduling problems have become increasingly significant. This paper deals with two NP-hard optimization problems: flexible job-shop scheduling problems (FJSPs) that encompass routing and sequencing sub-problems, and the FJSPs with process plan flexibility (FJSP-PPFs) that additionally include the process plan selection sub-problem. The study is carried out in two steps. In the first step, a mixed-integer linear programming model (MILP-1) is developed for FJSPs and compared to an alternative model in the literature (Model F) in terms of computational efficiency. In the second step, one other mixed-integer linear programming model, a modification of MILP-1, for the FJSP-PPFs is presented along with its computational results on hypothetically generated test problems.     

An exact algorithm for minimizing routing and operating costs in depot location

The problem of locating a single depot among n points is considered. The objective is to minimize the sum of depot operating cost and routing cost. The best depot location is found by means of an exact algorithm that determines simultaneously both the best depot location and the associated optimal delivery routes. A global integer programming formulation of the problem is given; the model is solved by relaxing most of its constraints and by introducing them only when they are violated.     

Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop

This paper considers the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. It continues recent work by Bräsel et al. [H. Bräsel, A. Herms, M. Mörig, T. Tautenhahn, T. Tusch, F. Werner, Heuristic constructive algorithms for open shop scheduling to minmize mean flow time, European J. Oper. Res., in press (doi.10.1016/j.ejor.2007.02.057)] on constructive algorithms. For this strongly NP-hard problem, we present two iterative algorithms, namely a simulated annealing and a genetic algorithm. For the simulated annealing algorithm, several neighborhoods are suggested and tested together with the control parameters of the algorithm. For the genetic algorithm, new genetic operators are suggested based on the representation of a solution by the rank matrix describing the job and machine orders. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The algorithms are compared relative to each other, and the quality of the results is also estimated partially by a lower bound for the corresponding preemptive open shop problem. For most of the problems, the genetic algorithm is superior when fixing the same number of 30 000 generated solutions for each algorithm. However, in contrast to makespan minimization problems, where the focus is on problems with an equal number of jobs and machines, it turns out that problems with a larger number of jobs than machines are the hardest problems.     

A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods

This paper proposes a new pro-active real-time control approach for dynamic vehicle routing problems in which the urgent delivery of goods is of utmost importance. Without assuming any distribution, stochastic knowledge about future requests is generated using past request information. The generated knowledge is integrated into the transportation process, which is controlled by a Tabu Search algorithm, in order to actively guide vehicles to request-likely areas before requests arrive there. By analyzing the results attained for various test settings, we identify structural diversity as a crucial criterion for classifying the quality of stochastic knowledge attainable from past request information. This criterion provides a promising starting point for assessing the quality of past request information in order to efficiently use the derived stochastic knowledge in real-time control approaches. We prove the efficiency of our approach by a direct comparison with a deterministic approach on test scenarios with varying structural diversity. Thanks to the proposed classification of structural diversity, differences in results obtained among the tested scenarios become explainable.     

An adaptive memory methodology for the vehicle routing problem with simultaneous pick-ups and deliveries

This paper deals with a routing problem variant which considers customers to simultaneously require delivery and pick-up services. The examined problem is referred to as the Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries (VRPSPD). VRPSPD is an NP-hard combinatorial optimization problem, practical large-scale instances of which cannot be solved by exact solution methodologies within acceptable computational times. Our interest was therefore focused on metaheuristic solution approaches. In specific, we introduce an Adaptive Memory (AM) algorithmic framework which collects and combines promising solution features to generate high-quality solutions. The proposed strategy employs an innovative memory mechanism to systematically maximize the amount of routing information extracted from the AM, in order to drive the search towards diverse regions of the solution space. Our metaheuristic development was tested on numerous VRPSPD instances involving from 50 to 400 customers. It proved to be rather effective and efficient, as it produced high-quality solutions, requiring limited computational effort. Furthermore, it managed to produce several new best solutions.     

Two approaches to optimal routing and admission control in systems with real-time traffic

This paper addresses the problem of routing and admission control of real-time traffic in a queueing system where customers must begin service within given deadlines (or complete service within given deadlines), otherwise they are considered lost. Performance in such systems is measured by the probability a customer is lost. For a system ofK parallel servers with a probabilistic routing and admission control scheme, the problem of the optimal routing and admission control is considered and two approaches are presented. Assuming the availability of a closed-form expression for the probability of loss at each server, the problem is solved under general conditions and properties of the optimal flow allocation are given. However, such closed-form expressions are often unavailable. This motivates a second approach, which involves a gradient-based stochastic optimization algorithm with on-line gradient estimation. The gradient estimation problem for loss probabilities is solved through a recently-developed smoothed perturbation analysis (SPA) technique. The effectiveness of on-line stochastic optimization using this type of gradient estimator is demonstrated by combining the SPA algorithm with a sampling-controlled stochastic optimization algorithm for the aforementioned routing and admission control problem.This work was supported in part by the Office of Naval Research under Contract N00014-87-K-0304, by the Rome Air Development Center under Contract F30602-88-D-0027, by NASA under Contract NAG 2-595, and by the National Science Foundation under Grant EID-92-12122.The authors are grateful to Don Towsley for several contributions to Section 2 and to an anonymous reviewer for pointing out a redundant assumption in the proof of Lemma 2.1.     

The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology

In this paper, we present a two-echelon capacitated electric vehicle routing problem with battery swapping stations (2E-EVRP-BSS), which aims to determine the delivery strategy under battery driving range limitations for city logistics. The electric vehicles operating in the different echelons have different load capacities, battery driving ranges, power consumption rates, and battery swapping costs. We propose an integer programming formulation and a hybrid algorithm that combines a column generation and an adaptive large neighborhood search (CG-ALNS) to solve the problem. We conducted extensive computational experiments, demonstrate the applicability of the proposed model, and show the efficiency of the CG-ALNS algorithm. In addition, we explore the interplay between battery driving range and the effectiveness of vehicle emission reduction through sensitivity analysis.     

Using parallel & distributed computing for real-time solving of vehicle routing problems with stochastic demands

This paper focuses on the Vehicle Routing Problem with Stochastic Demands (VRPSD) and discusses how Parallel and Distributed Computing Systems can be employed to efficiently solve the VRPSD. Our approach deals with uncertainty in the customer demands by considering safety stocks, i.e. when designing the routes, part of the vehicle capacity is reserved to deal with potential emergency situations caused by unexpected demands. Thus, for a given VRPSD instance, our algorithm considers different levels of safety stocks. For each of these levels, a different scenario is defined. Then, the algorithm solves each scenario by integrating Monte Carlo simulation inside a heuristic-randomization process. This way, expected variable costs due to route failures can be naturally estimated even when customers’ demands follow a non-normal probability distribution. Use of parallelization strategies is then considered to run multiple instances of the algorithm in a concurrent way. The resulting concurrent solutions are then compared and the one with the minimum total costs is selected. Two numerical experiments allow analyzing the algorithm’s performance under different parallelization schemas.     

Separable routing: A scheme for state-dependent routing of circuit switched telephone traffic

Separable routing is the first of a number of routing schemes for circuit switched telephone traffic invented at Bellcore. These routing schemes are state dependent, in the sense that, for each call attempt, a routing decision is made on the basis of the state of the network (defined in terms of the numbers of busy and idle trunks in the various trunk groups at the moment of the call attempt). In this paper, we describe separable routing and its mathematical background. Simulation results we have presented elsewhere show that the family of state-dependent routing schemes, of which separable routing is a member, is very attractive in terms of blocking rate, built-in network management features, and behavior in the presence of traffic forecast error.     

A mean value for games with communication structures

The mean value is a new extension of the Shapley value for games with communication structure representable by a simple graph; only pairwise meetings can occur, although some of them might not be permitted. The new value is characterized by a set of axioms of which the one with the most far-reaching effect is an associated consistency property already used in various contexts. The mean value of an n-player unanimity game is the arithmetic average of the mean values of (n–1)-player unanimity games with connected support, which means games in which the deleted players are not articulation point of the considered graph.I wish to thank the anonymous referees for their helpful remarks. The usual disclaimer applies.Received: April 2002/Accepted: February 2004     

Vehicle routing with dynamic travel times: A queueing approach

Transportation is an important component of supply chain competitiveness since it plays a major role in the inbound, inter-facility, and outbound logistics. In this context, assigning and scheduling vehicle routes is a crucial management problem. In this paper, a vehicle routing problem with dynamic travel times due to potential traffic congestion is considered. The approach developed introduces mainly the traffic congestion component based on queueing theory. This is an innovative modeling scheme to capture travel times. The queueing approach is compared with other approaches and its potential benefits are described and quantified. Moreover, the optimization of the starting times of a route at the distribution center is evaluated. Finally, the trade-off between solution quality and calculation time is discussed. Numerous test instances are used, both to illustrate the appropriateness of the approach as well as to show that time-independent solutions are often unrealistic within a congested traffic environment, which is usually the case on European road networks.     

A route-neighborhood-based metaheuristic for vehicle routing problem with time windows

In this paper, a two-stage metaheuristic based on a new neighborhood structure is proposed to solve the vehicle routing problem with time windows (VRPTW). Our neighborhood construction focuses on the relationship between route(s) and node(s). Unlike the conventional methods for parallel route construction, we construct routes in a nested parallel manner to obtain higher solution quality. Valuable information extracted from the previous parallel construction runs is used to enhance the performance of parallel construction. In addition, when there are only a few unrouted customers left, we design a special procedure for handling them. Computational results for 60 benchmark problems are reported. The results indicate that our approach is highly competitive with all existing heuristics, and in particular very promising for solving problems of large size.     

A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs

Recent years have seen growing interest in coherent risk measures, especially in Conditional Value-at-Risk ( \(\mathrm {CVaR}\) ). Since \(\mathrm {CVaR}\) is a convex function, it is suitable as an objective for optimization problems when we desire to minimize risk. In the case that the underlying distribution has discrete support, this problem can be formulated as a linear programming (LP) problem. Over more general distributions, recent techniques, such as the sample average approximation method, allow to approximate the solution by solving a series of sampled problems, although the latter approach may require a large number of samples when the risk measures concentrate on the tail of the underlying distributions. In this paper we propose an automatic primal-dual aggregation scheme to exactly solve these special structured LPs with a very large number of scenarios. The algorithm aggregates scenarios and constraints in order to solve a smaller problem, which is automatically disaggregated using the information of its dual variables. We compare this algorithm with other common approaches found in related literature, such as an improved formulation of the full problem, cut-generation schemes and other problem-specific approaches available in commercial software. Extensive computational experiments are performed on portfolio and general LP instances.     

A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem

In this paper, a particle swarm optimization algorithm (PSO) is presented to solve the permutation flowshop sequencing problem (PFSP) with the objectives of minimizing makespan and the total flowtime of jobs. For this purpose, a heuristic rule called the smallest position value (SPV) borrowed from the random key representation of Bean [J.C. Bean, Genetic algorithm and random keys for sequencing and optimization, ORSA Journal of Computing 6(2) (1994) 154–160] was developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems. In addition, a very efficient local search, called variable neighborhood search (VNS), was embedded in the PSO algorithm to solve the well known benchmark suites in the literature. The PSO algorithm was applied to both the 90 benchmark instances provided by Taillard [E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research, 64 (1993) 278–285], and the 14,000 random, narrow random and structured benchmark instances provided by Watson et al. [J.P. Watson, L. Barbulescu, L.D. Whitley, A.E. Howe, Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance, ORSA Journal of Computing 14(2) (2002) 98–123]. For makespan criterion, the solution quality was evaluated according to the best known solutions provided either by Taillard, or Watson et al. The total flowtime criterion was evaluated with the best known solutions provided by Liu and Reeves [J. Liu, C.R. Reeves, Constructive and composite heuristic solutions to the P∥∑C_i scheduling problem, European Journal of Operational Research 132 (2001) 439–452], and Rajendran and Ziegler [C. Rajendran, H. Ziegler, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155(2) (2004) 426–438]. For the total flowtime criterion, 57 out of the 90 best known solutions reported by Liu and Reeves, and Rajendran and Ziegler were improved whereas for the makespan criterion, 195 out of the 800 best known solutions for the random and narrow random problems reported by Watson et al. were improved by the VNS version of the PSO algorithm.