A Genetic Algorithm to Minimize the Makespan in a Two-Machine Cross-Docking Flow Shop Problem
- PDF / 737,274 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 206 Views
A Genetic Algorithm to Minimize the Makespan in a Two-Machine Cross-Docking Flow Shop Problem Imen Hamdi1,2 · Mohamed Fadhel Tekaya1 Received: 26 October 2018 / Revised: 15 May 2019 / Accepted: 31 October 2019 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract We consider the problem of two-machine cross-docking flow shop scheduling where each job on the second machine cannot be processed unless a job or a set of jobs have been completed on the first machine. The aim is to find a feasible schedule that minimizes the makespan. As the problem is shown to be strongly NP-hard, we propose a genetic algorithm to solve small and large size problems. We test different types for each genetic operator where new ideas are introduced, which leads to propose six versions of the genetic algorithm. We then evaluate their effectiveness through an extensive computational experiments by using many instances generated randomly and by determining the percentage deviation from a lower bound from the literature. Keywords Cross-docking · Flow shop · Scheduling · Makespan · Genetic algorithm Mathematics Subject Classification 90B35
1 Introduction Cross-docking is a kind of warehouse considered as an intermediate node in a distribution network. It aims to consolidate shipments which have different sizes with the same destination to full track loads. The shipments are unloaded from inbound trucks, sorted and categorized according to their characteristics, transferred and loaded onto outbound trucks for delivery to demand points without storage in between with minimum standby time (less than or equal to 24 h) (Bartholdi et al. [1], Li et al. [2], Vahdani and Zandieh [3]). Kinnear [4] defined the cross-docking as “ receiving
B
Imen Hamdi [email protected] Mohamed Fadhel Tekaya [email protected]
1
High Institute of Transport and Logistics, University of Sousse, Sousse, Tunisia
2
MODILS lab, Faculty of Economics and Management, University of Sfax, Sfax, Tunisia
123
I. Hamdi, M. F. Tekaya
product from a supplier or manufacturer for several end destinations and consolidating this product with other supplier’s product for common final delivery destinations”. Then, cross-docking provides great economies in transportation costs including warehousing, transportation, inventory-holding costs, handling costs, labor costs, and maintenance while improving client satisfaction, reducing the storage space and reducing risk for loss and damage. Generally, in the cross-dock, there are two main tasks: unloading inbound trucks and loading outbound trucks, which are typically separated by some intermediate activities including scanning, sorting, and shipping. These two tasks are to be processed by the resources “dock doors”, which can process one truck at a time and are assumed to be sufficiently equipped with loading equipment and workers. In this research, we consider the case of only one outbound trailer and one inboun
Data Loading...
