Title: Online scheduling of flexible job-shops with blocking and transportation

Authors: Jens Poppenborg; Sigrid Knust; Joachim Hertzberg

Addresses: Clausthal University of Technology, Institute of Applied Stochastics and Operations Research, 38678 Clausthal-Zellerfeld, Germany. ' University of Osnabrück, Institute of Computer Science, 49069 Osnabrück, Germany. ' University of Osnabrück, Institute of Computer Science, 49069 Osnabrück, Germany

Abstract: This paper deals with online scheduling of a flexible job-shop with blocking where jobs are transported between the machines by one or several automated guided vehicles. The objective is to minimise the total weighted tardiness of the jobs. Schedules have to be generated online (i.e., jobs only become known to the scheduler at their respective release dates) as well as in real time (i.e., only a limited amount of computation time is allowed). We propose a MIP formulation for the offline situation and an online Tabu search algorithm that decomposes the problem into an assignment and a scheduling subproblem. In some computational experiments online and offline algorithms are compared for various problem instances. [Received 17 May 2010; Revised 24 November 2010; Accepted 24 February 2011]

Keywords: job shop scheduling; online scheduling; flexible job shops; automated guided vehicles; AGVs; blocking; total weighted tardiness; tabu search.

DOI: 10.1504/EJIE.2012.047662

European Journal of Industrial Engineering, 2012 Vol.6 No.4, pp.497 - 518

Published online: 10 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article