Tabu search and lower bounds for a combined production-transportation problem

Autor(en): Condotta, Alessandro
Knust, Sigrid 
Meier, Dimitri
Shakhlevich, Natalia V. 
Stichwörter: ALGORITHM; BATCH; Batching; Computer Science; Computer Science, Interdisciplinary Applications; DELIVERY; Engineering; Engineering, Industrial; FLOW-SHOP; JOBS; Lower bounds; MACHINES; MINIMIZING MAKESPAN; NEIGHBORHOOD SEARCH; Operations Research & Management Science; RELEASE; Scheduling; Tabu search; Transportation
Erscheinungsdatum: 2013
Volumen: 40
Ausgabe: 3
Startseite: 886
Seitenende: 900
In this paper we consider a combined production-transportation problem, where n jobs have to be processed on a single machine at a production site before they are delivered to a customer. At the production stage, for each job a release date is given; at the transportation stage, job delivery should be completed not later than a given due date. The transportation is done by m identical vehicles with limited capacity. It takes a constant time to deliver a batch of jobs to the customer. The objective is to find a feasible schedule minimizing the maximum lateness. After formulating the considered problem as a mixed integer linear program, we propose different methods to calculate lower bounds. Then we describe a tabu search algorithm which enumerates promising partial solutions for the production stage. Each partial solution is complemented with an optimal transportation schedule (calculated in polynomial time) achieving a coordinated solution to the combined production-transportation problem. Finally, we present results of computational experiments on randomly generated data. (C) 2012 Elsevier Ltd. All rights reserved.
ISSN: 03050548
DOI: 10.1016/j.cor.2012.08.017

Show full item record

Page view(s)

Last Week
Last month
checked on Feb 23, 2024

Google ScholarTM