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 | Herausgeber: | PERGAMON-ELSEVIER SCIENCE LTD | Journal: | COMPUTERS & OPERATIONS RESEARCH | Volumen: | 40 | Ausgabe: | 3 | Startseite: | 886 | Seitenende: | 900 | Zusammenfassung: | 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 |
Zur Langanzeige
Seitenaufrufe
6
Letzte Woche
0
0
Letzter Monat
1
1
geprüft am 08.05.2024