0000000000147268
AUTHOR
José Manuel Tamarit
New exact methods for the time-invariant berth allocation and quay crane assignment problem
Abstract Efficient management of operations in seaport container terminals has become a critical issue, due to the increase in maritime traffic and the strong competition between ports. In this paper we focus on two seaside operational problems: the Berth Allocation Problem and the Quay Crane Assignment Problem, which are considered in an integrated way. For the continuous BACAP problem with time-invariant crane assignment we propose a new mixed integer linear model in which the vessels can be moored at any position on the quay, not requiring any quay discretization. The model is enhanced by adding several families of valid inequalities. The resulting model is able to solve instances with u…
A Maximal-Space Algorithm for the Container Loading Problem
In this paper, a greedy randomized adaptive search procedure (GRASP) for the container loading problem is presented. This approach is based on a constructive block heuristic that builds upon the concept of maximal space, a nondisjoint representation of the free space in a container. This new algorithm is extensively tested over the complete set of Bischoff and Ratcliff problems [Bischoff, E. E., M. S. W. Ratcliff. 1995. Issues in the development of approaches to container loading. Omega 23 377–390], ranging from weakly heterogeneous to strongly heterogeneous cargo, and outperforms all the known nonparallel approaches that, partially or completely, have used this set of test problems. When …
Determining the best shipper sizes for sending products to customers
A distribution company has to send products, packed into shippers, from the warehouse to retail shops. The number of different shipper types is regarded as a parameter given by the user, who is looking for a balance between transportation costs and stock and procurement costs. The problem is to decide the sizes of the shipper types to keep at the warehouse so as to minimize the cost of meeting the forecasted demand over the planning horizon. In this paper, we describe an integer linear programming formulation for the problem and obtaining feasible solutions. Other models, based on multiknapsack and p-median and facility location models, are for obtaining lower bounds. We study several ways …
A tabu search algorithm for a two-dimensional non-guillotine cutting problem
In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.
Design and implementation of a course scheduling system using Tabu Search
Abstract Building a course timetable is a difficult and lengthy task which universities devote a large amount of human and material resources to every year. We have developed a computer package to solve this problem. The program runs on a PC and the user may set the objectives and parameters from among a wide range of possibilities. It has a user-friendly interface for the user to input the relevant data and obtain the corresponding results. The optimization process is based on a set of heuristic algorithms. The core is a Tabu Search procedure for which several strategies have been developed and tested in order to get a fast and powerful algorithm. The first tests of the package have produc…
Partially Renewable Resources
In recent years, in the field of project scheduling the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this chapter we define this type of resource, describe an integer linear formulation and present some examples of conditions appearing in real problems which can be modeled using partially renewable resources. Then we introduce some preprocessing procedures to identify infe…
A reactive GRASP algorithm for the container loading problem with load-bearing constraints
The container loading problem consists in packing a set of boxes of different dimensions into a large container of fixed dimensions, usually with the objective of maximising the container load. In practical problems, besides the geometric constraints of not exceeding the container dimensions and ensuring the non-overlapping of boxes, other requirements may appear, such as total weight, weight balance or support. In this paper we address the problem of maximising container volume utilisation while respecting a set of practical constraints: full support of boxes, allowed orientations and load-bearing capacity. We have developed different heuristics for solving the problem and we have combined…
A branch-and-cut algorithm for the pallet loading problem
We propose a branch-and-cut algorithm for the pallet loading problem. The 0-1 formulation proposed by Beasley for cutting problems is adapted to the problem, adding new constraints and new procedures for variable reduction. We then take advantage of the relationship between this problem and the maximum independent set problem to use the partial linear description of its associated polyhedron. Finally, we exploit the specific structure of our problem to define the solution graph and to develop efficient separation procedures. We present computational results for the complete sets Cover I (up to 50 boxes) and Cover II (up to 100 boxes).
GRASP and path relinking for project scheduling under partially renewable resources
[EN] Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this paper, we develop some preprocessing techniques and several heuristic algorithms for the problem. Preprocessing significantly reduces the dimension of the problems, therefore improving the efficiency of solution procedures. Heuristic algorithms based on GRASP an…
A GRASP algorithm for constrained two-dimensional non-guillotine cutting problems
This paper presents a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional non-guillotine cutting problem, the problem of cutting the rectangular pieces from a large rectangle so as to maximize the value of the pieces cut. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures.
A heuristic to schedule flexible job-shop in a glass factory
We describe the design and implementation of a scheduling system in a glass factory. The factory produces a large variety of manufactured glass objects in a complex process ranging from melting the glass in the furnaces and blowing it automatically or manually to decorating, assembling and packing it. The structure basically corresponds to a flexible job-shop scheduling problem with some special characteristics. On the one hand, dealing with hot liquid glass imposes no-wait constraints on some operations. On the other hand, skilled workers performing some manual tasks are modelled as special machines. The system produces approximate solutions in very short computing times, trying to minimiz…
A computational study of LP-based heuristic algorithms for two-dimensional guillotine cutting stock problems
In this paper we develop and compare several heuristic methods for solving the general two-dimensional cutting stock problem. We follow the Gilmore-Gomory column generation scheme in which at each iteration a new cutting pattern is obtained as the solution of a subproblem on one stock sheet. For solving this subproblem, in addition to classical dynamic programming, we have developed three heuristic procedures of increasing complexity, based on GRASP and Tabu Search techniques, producing solutions differing in quality and in time requirements. In order to obtain integer solutions from the fractional solutions of the Gilmore-Gomory process, we compare three rounding procedures, rounding up, t…
A GRASP/Path Relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems
The three-dimensional multiple bin-size bin packing problem, MBSBPP, is the problem of packing a set of boxes into a set of bins when several types of bins of different sizes and costs are available and the objective is to minimize the total cost of bins used for packing the boxes. First we propose a GRASP algorithm, including a constructive procedure, a postprocessing phase and some improvement moves. The best solutions obtained are then combined into a Path Relinking procedure for which we have developed three versions: static, dynamic and evolutionary. An extensive computational study, using two- and three-dimensional instances, shows the relative efficiency of the alternatives considere…
A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems
Abstract In this paper we develop several heuristic algorithms for the two-dimensional cutting problem (TDC) in which a single stock sheet has to be cut into a set of small pieces, while maximising the value of the pieces cut. They can be considered to be general purpose algorithms because they solve the four versions of the TDC: weighted and unweighted, constrained and unconstrained. We begin by proposing two constructive procedures based on simple bounds obtained by solving one-dimensional knapsack problems. We then use these constructive algorithms as building blocks for more complex procedures. We have developed a greedy randomised adaptive search procedure (GRASP) which is very fast an…
Reactive GRASP for the strip-packing problem
This paper presents a greedy randomized adaptive search procedure (GRASP) for the strip packing problem, which is the problem of placing a set of rectangular pieces into a strip of a given width and infinite height so as to minimize the required height. We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well-known instances which have been previously reported, first to select the best alternatives and then to compare the efficiency of our algorithm with other procedures. The results show that the GRASP algorithm outperforms recently reported metaheuristics.
GRASP and Path Relinking for the Two-Dimensional Two-Stage Cutting-Stock Problem
We develop a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional two-stage cutting-stock problem. This is a special cutting problem in which the cut is performed in two phases. In the first phase, the stock rectangle is slit down its width into different vertical strips and in the second phase, each of these strips is processed to obtain the final pieces. We propose two different algorithms based on GRASP methodology. One is “piece-oriented” while the other is “strip-oriented.” Both procedures are fast and provide solutions of different structures to this cutting problem. We also propose a path-relinking algorithm, which operates on a set of elite soluti…
Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics
We consider the problem of scheduling a set of jobs on a set of identical parallel machines where the objective is to minimize the total weighted earliness and tardiness penalties with respect to a common due date. We propose a hybrid heuristic algorithm for constructing good solutions, combining priority rules for assigning jobs to machines and a local search with exact procedures for solving the one-machine subproblems. These solutions are then used in two metaheuristic frameworks, Path Relinking and Scatter Search, to obtain high quality solutions for the problem. The algorithms are tested on a large number of test instances to assess the efficiency of the proposed strategies. The result…
Algorithms for Pallet Building and Truck Loading in an Interdepot Transportation Problem
This paper deals with the problem of a logistics company that has to serve its customers by first putting the products on pallets and then loading the pallets into trucks. Besides the standard geometric constraints of products not overlapping each other and not exceeding the dimensions of pallets and trucks, in this real problem, there are many other constraints, related to the total weight of the load, the maximum weight supported by each axle, and the distribution of the load inside the truck. Although the problem can be decomposed into two phases, pallet loading and truck loading, we have taken a combined approach, building and placing pallets at the same time. For each position in the t…
Labour Scheduling at an Airport Refuelling Installation
We have developed an automatic assignment procedure for labour scheduling at a continously operating airport refuelling installation. Different types of workers are subject to different conditions on the shifts they can do (morning, evening or night), shift lengths, days-off, holidays, terms of contract and working hours. The scheduling process is carried out on a weekly basis, but there are mid-term and long-term conditions and objectives which link each week with the preceding and following weeks. Our package uses firstly a tabu search algorithm to find the best schemes of shifts/days-off to be used to cover the requirements. Secondly, an assignment problem is solved to match the schemes …
Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts
Abstract This paper presents an approach for solving a new real problem in cutting and packing. At its core is an innovative mixed integer programme model that places irregular pieces and defines guillotine cuts. The two-dimensional irregular shape bin packing problem with guillotine constraints arises in the glass cutting industry, for example, the cutting of glass for conservatories. Almost all cutting and packing problems that include guillotine cuts deal with rectangles only, where all cuts are orthogonal to the edges of the stock sheet and a maximum of two angles of rotation are permitted. The literature tackling packing problems with irregular shapes largely focuses on strip packing i…
The continuous Berth Allocation Problem in a container terminal with multiple quays
We propose an integer linear model for the case of BAP with multiple quays.We design several constructive procedures and propose a large set of priority rules.We design a genetic algorithm, using the solutions obtained by the priority rules.For BAP with one quay, our genetic algorithm outperforms the best published methods. This paper extends the study of the continuous Berth Allocation Problem to the case of multiple quays, which is found in many container terminals around the world. Considering multiple quays adds a problem of assigning vessels to quays to the problem of determining berthing times and positions for each incoming vessel.This problem has not been considered in the literatur…
Constructing Good Solutions for the Spanish School Timetabling Problem
In the school timetabling problem a set of lessons (combinations of classes, teachers, subjects and rooms) has to be scheduled within the school week. Considering classes, teachers and rooms as resources for the lessons, the problem may be viewed as the scheduling of a project subject to resource constraints. We have developed an algorithm with three phases. In Phase I an initial solution is built by using the scheme of parallel heuristic algorithm with priority rules, but imbedding at each period the construction of a maximum cardinality independent set on a resource graph. In Phase II a tabu search procedure starts from the solution of Phase I and obtains a feasible solution to the proble…
Mathematical models for multicontainer loading problems
Abstract This paper deals with the problem of a distribution company that has to serve its customers by putting first the products on pallets and then loading the pallets onto trucks. We approach the problem by developing and solving integer linear models. We start with basic models, that include the essential features of the problem, such as respecting the dimensions of the truck, and not exceeding the total weight capacity and the maximum weigh capacity on each axle. Then, we add progressively new conditions to consider the weight and volume of pallet bases and to include other desirable features for the solutions to be useful in practice, such as the position of the center of gravity and…
Matheuristics for the irregular bin packing problem with free rotations
[EN] We present a number of variants of a constructive algorithm able to solve a wide variety of variants of the Two-Dimensional Irregular Bin Packing Problem (2DIBPP). The aim of the 2DIBPP is to pack a set of irregular pieces, which may have concavities, into stock sheets (bins) with fixed dimensions in such a way that the utilization is maximized. This problem is inspired by a real application from a ceramic company in Spain. In addition, this problem arises in other industries such as the garment industry or ship building. The constructive procedure presented in this paper allows both free orientation for the pieces, as in the case of the ceramic industry, or a finite set of orientation…