A reconfigurable manufacturing system (RMS) is a new paradigm for the manufacturing environment to respond to unpredictable market change and frequent new product introduction. One of the components of an RMS is a reconfigurable material handling system (RMHS). This paper investigates the permutation flow shop scheduling problem in a manufacturing system with RMHS. Hence, first, a novel Mixed Integer Linear Programming (MILP) model is developed. Then, to tackle the inherent complexity of the problem, an efficient constraint programming (CP) approach is devised. Finally, comprehensive computational experiments are conducted to evaluate the performance of both models, followed by a sensitivity analysis on three key performance indicators to further assess the CP model and extract the managerial insights. Results show that the CP model has better performance than the MILP model for solving large-scale problem instances and achieves a high-quality solution in a reasonable time. Moreover, the flexibility of eligibility restrictions can significantly affect the Makespan and solution time.