The Jaya algorithm is a novel, simple, and efficient meta-heuristic optimization technique and has received a successful application in the various fields of engineering and sciences. In the present paper, we apply the Jaya algorithm to permutation flow shop scheduling problem (PFSP) with the multi-objective of minimization of maximum completion time (makespan) and tardiness cost under due date constraints. PFSP is a well-known NP-hard and discrete combinatorial optimization problem. Firstly, to retrieve a job sequence, a random preference is allocated to each job in a permutation schedule. Secondly, a job preference vector is transformed into a job permutation vector by means of largest order value (LOV) rule. To deal with the multi-objective criteria, we apply a multi-attribute model (MAM) based on Apriori approach. The correctness of the Jaya algorithm is verified by comparing the results with the total enumeration method and simulated annealing (SA) algorithm. Computational results reveal that the proposed optimization technique is well efficient in solving multi-objective discrete combinatorial optimization problems such as the flow shop scheduling problem in the present study. © Springer Nature Singapore Pte Ltd. 2020.