ABSTRACT
Two hybrid flow shop scheduling lines must be coordinated to assemble batches of terminated products at their last stage. Each product is thus composed of two jobs, each produced in one of the lines. The set of jobs is to be processed in a series of stages to minimize the makespan of the scheduling, but jobs forming a product must arrive at the assembly line simultaneously. We propose a mixed integer linear programming model. Then, based on the model, we propose a pull-matheuristic algorithm. Finally, we present two metaheuristics, a greedy randomized adaptive search procedure and a biased random key genetic algorithm, and compare all the methodologies with real-based instances of a production scheduling problem in the automobile manufacturing industry. The greedy algorithm yields high-quality solutions, while the genetic one offers the best computational times.
Subject(s)
Algorithms , Models, Theoretical , AutomobilesABSTRACT
Real-time control strategies deal with the day's dynamics in bus rapid transit systems. This work focuses on minimizing the number of buses of the same line cruising head-to-tail or arriving at a stop simultaneously by implementing bus holding times at the stops as a control strategy. We propose a new mathematical model to determine the bus holding times. It has quadratic constraints but a linear objective function that minimizes the bus bunching penalties. We also propose a beam-search heuristic to reduce computational solution time to solve large instances. Experimental results on a bus rapid transit system simulation in Monterrey, Mexico, show a bus bunching reduction of 45% compared to the case without optimization. Moreover, passenger waiting times are reduced by 30% in some scenarios. For real-world instances with 60 buses, the beam-search approach provides solutions with an optimality gap of less than 5% in less than 3 s.
ABSTRACT
We use the Positions and Covering methodology to obtain exact solutions for the two-dimensional, non-guillotine restricted, strip packing problem. In this classical NP-hard problem, a given set of rectangular items has to be packed into a strip of fixed weight and infinite height. The objective consists in determining the minimum height of the strip. The Positions and Covering methodology is based on a two-stage procedure. First, it is generated, in a pseudo-polynomial way, a set of valid positions in which an item can be packed into the strip. Then, by using a set-covering formulation, the best configuration of items into the strip is selected. Based on the literature benchmark, experimental results validate the quality of the solutions and method's effectiveness for small and medium-size instances. To the best of our knowledge, this is the first approach that generates optimal solutions for some literature instances for which the optimal solution was unknown before this study.
Subject(s)
Algorithms , Computer SimulationABSTRACT
We present a two-stage methodology called Positions and Covering (P&C) to solve the two-dimensional bin packing problem (2D-BPP). The objective of this classical combinatorial NP-hard problem is to pack a set of items (small rectangles) in the minimum number of bins (larger rectangles). The first stage is the key-point of the Positions and Covering, where for each item, it is generated in a pseudo-polynomial way a set of valid positions that indicate the possible ways of packing the item into the bin. In the second stage, a new set-covering formulation, strengthen with three sets of valid inequalities, is used to select the optimal non-overlapping configuration of items for each bin. Experimental results for the P&C method are presented and compared with some of the best algorithms in the literature for small and medium size instances. Furthermore, we are considering both cases of the 2D-BPP, with and without rotations of the items by 90°. To the best of our knowledge, this is one of the first exact approaches to obtain optimal solutions for the rotation case.
