Open AccessAnalysis of flow shop problems and their algorithms
Author(s) -
Lina Rajeckaitė,
Narimantas Listopadskis
Publication year - 2009
Publication title -
lietuvos matematikos rinkinys
Language(s) - English
Resource type - Journals
eISSN - 2335-898X
pISSN - 0132-2818
DOI - 10.15388/lmr.2009.38
Subject(s) - job shop scheduling , tabu search , unavailability , flow shop scheduling , heuristics , simulated annealing , mathematical optimization , computer science , scheduling (production processes) , combinatorial optimization , branch and bound , schedule , open shop scheduling , algorithm , mathematics , statistics , operating system
The combinatorial optimization problem considered in this paper is flow shop scheduling problem arising in logistics, management, business, manufacture and etc. A set of machines and a set of jobs are given. Each job consists of a set of operations. Machines are working with unavailability intervals. The task is to minimize makespan, i.e. the overall length of the schedule. There is overview of combinatorial optimization, scheduling problems and methods used to solve them. There is also presented and realized one exact algorithm – Branch and Bound, and two meta-heuristics: Simulated Annealing and Tabu Search. Analysis of these three algorithms is made.