In this paper, we consider a flow shop scheduling problem with availability constraints (FSSPAC) for the objective of minimizing the makespan. In such a problem, machines are not continuously available for processing jobs due to preventive maintenance activities. We proposed a mixed-integer linear programming (MILP) model for this problem which can generate non-permutation schedules. Furthermore, an improving heuristic method and a genetic algorithm (GA) based heuristic are developed to evolve optimal or near optimal solutions. To obtain better and more robust solutions, The Taguchi method is performed for tuning the parameters of genetic algorithm. The MILP model can be used to compute optimal solutions for small-sized problems or to test the performance of solution algorithms. The presented methodology is evaluated for the solution quality. According to computational experiments, the GA can reach good-quality solutions in reasonable computational time, and can be used to solve large scale problems effectively.