A hybrid Genetic Algorithm for the Heterogeneous Dial-A-Ride Problem
A new hybrid Genetic Algorithm for the Heterogeneous Dial-A-Ride Problem (H-DARP).Efficient crossover operators and local search techniques.Experiments on existing DARP and H-DARP instances and new, larger, H-DARP instances.Computational experiments ...
A Combined column generation and heuristics for railway short-term rolling stock planning with regular inspection constraints
The aim of railway rolling stock planning problem is to find an optimal allocation of train-sets for a given set of trips in the train timetable in order to minimize the total cost. We propose a column generation and Lagrangian relaxation heuristics for ...
Mixed integer linear programming models for optimal crop selection
Two MILP models for an optimal crop selection problem are given.Resource requests and timing of operations are deterministic; prices and yields are stochastic.The first model maximizes the expected profit on average data.The second model uses ...
Minimizing CO2 emissions in a practical daily carpooling problem
Two mathematical formulations and two efficient heuristic algorithms are proposed.A prototype of the web application is developed to support carpooling at the company.Computational experiments indicate high potential for reductions in CO2 ...
A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
A heuristic framework for a class of robust optimization problems is proposed.The heuristic framework explores dual information.The heuristic is successfully applied to solve two robust optimization problems.The heuristic is able to outperform a widely ...
Delay-constrained routing problems
We extend previously available models of delay-constrained routing problems.We account for the latency formulae of the most relevant classes of GPS-derived schedulers from the literature.We explicitly introduce the concept of admission control ...
An effective iterated tabu search for the maximum bisection problem
Max-bisection is a challenging optimization problem with important applications.An iterated tabu search (ITS) is proposed based on two move operators (1-move and swap).Effective data structures using bucket sorting are used to streamline the ...
Scheduling on parallel processors with varying processing times
The parallel processor makespan minimization with general position dependent models is considered.An exact parallel fast dynamic programing algorithm is constructed.Fully polynomial time approximation schemes are provided. In this paper, we construct ...
Exact and heuristic approaches based on noninterfering transmissions for joint gateway selection, time slot allocation, routing and power control for wireless mesh networks
Tactical and operational problems of wireless mesh networks are jointly considered.Mixed integer linear programming formulations and a valid inequality are proposed.Necessary and sufficient conditions for simultaneous transmissions are derived.Heuristic ...
Achieving full connectivity of sites in the multiperiod reserve network design problem
The problem of Conservation Planning over time by considering spatial connectivity of the selected sites.We propose a multi-period MIP model for the dynamic reserve network design problem.It selects a fully connected subset of sites for a cost-effective ...
A Benders decomposition based framework for solving cable trench problems
Algorithmic framework based on Benders decomposition applicable to different variants of the cable trench problem (CTP).Benders decomposition approach including stabilization and primal heuristics.Computational study addressing three variants of the ...
On the exact solution of the no-wait flow shop problem with due date constraints
Five different mathematical programming models and two constraint programming models are developed for the no-wait flow shop problem with due date constraints.Unique characteristics of the problem are discussed and a number of propositions are proved; ...
An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem
We present a new iterated greedy algorithm for the permutation flowshop problem under makespan objective.Our algorithm applies local search on partial solutions after the destruction phase.Our algorithm compares favorably with others from the literature ...
A beam-search-based constructive heuristic for the PFSP to minimise total flowtime
In this paper we present a beam-search-based constructive heuristic to solve the permutation flowshop scheduling problem with total flowtime minimisation as objective. This well-known problem is NP-hard, and several heuristics have been developed in the ...
Designing and constructing networks under uncertainty in the construction stage
Novel Network Optimization problem combining network design and network construction scheduling under uncertainty.Modeling framework: design decision depends on the design costs and also on the corresponding construction plan.MIP formulations and an ...
An iterated tabu search for the multi-compartment vehicle routing problem
We study a practical variant of the vehicle routing problem with compartments.We propose a heuristic solution using tabu search embedded in iterated local search.We report results of experiments which analyze the heuristic performance in detail.We find ...
Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties
- Bruno Ferreira Rosa,
- Marcone Jamilson Freitas Souza,
- Sérgio Ricardo de Souza,
- Moacir Felizardo de França Filho,
- Zacharie Ales,
- Philippe Yves Paul Michelon
A novel idle time insertion algorithm.A new algorithm of implicit enumeration.A new efficient heuristic algorithm for solving the addressed problem. This paper addresses the single machine scheduling problem with distinct time windows and sequence-...
Integrating large positive and negative performance differences into multicriteria majority-rule sorting models
We extend MR-Sort to include large positive and negative performance differences.We propose exact algorithms to elicit the parameters of the models.The proposed approaches are tested on artificially constructed benchmarks.The results show the ...
Optimal distributed task scheduling in volunteer clouds
A framework for task scheduling policies in a large-scale distributed cloud.A mathematical formulation driven by real system requirements.Model with: FIFO queue, tasks with deadlines, the actual load on the machines.Application of the distributed ...
An exact algorithm for a Vehicle-and-Driver Scheduling Problem
We introduce the Vehicle-and-Driver Scheduling Problem (VDSP), a new task scheduling problem that can be modeled as a two-depot vehicle routing problem with two types of vehicles, each type performing different kinds of routes.We propose a mixed integer ...
Spanning trees with a constraint on the number of leaves. A new formulation
New extended model for finding a minimum cost spanning tree such that the number of leaves is equal to (greater than, less than) k.Model with enhanced cut constraints.New model improves previously known gaps for the three constrained versions and leads ...
The probabilistic orienteering problem
A novel stochastic version of the orienteering problem is considered.The problem generalizes the probabilistic TSP.A deterministic equivalent MILP model is derived.A branch-and-cut procedure with special branching rules is developed.Matheuristic ...
Supplier selection and order allocation with green criteria
Green and traditional criteria for supplier selection were split into two sets.Two bi-objective and one multi-objective optimization models were proposed.The models use a combination of three tools: AHP, Fuzzy TOPSIS and optimization.The results show ...
Multiperiod portfolio investment using stochastic programming with conditional value at risk
Stagewise stochastic (integer) programming with CVaR for multiperiod portfolio investment are proposed.Heuristic moment matching method is utilized to generate scenarios for our models.The targets are the 50 listed companies with the greatest market ...
A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
We model the MBVP as an integer linear program with undirected variables.We derive valid inequalities for it and prove that some of these are facet defining.We develop a hybrid formulation containing undirected and directed variables.We solve both ...