| Abstract [eng] |
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 (SA) and Tabu Search (TS). Analysis of these three algorithms is made. The results showed that Branch and Bound is effective solving simple problems. While solving more complicated problems Tabu Search is more effective than Simulated Annealing. At the end of this paper we tell the decision about algorithms analyzed and recommendations about choosing suitable parameters. |
