Scheduling is the process of allocating resources to perform a set of tasks over a period of time to optimize the specified objective function. Our work focuses on developing the optimal solution or a lower bound for N-job, M-machine Permutation Flowshop Scheduling (PFS) problem in a manufacturing system with the objective of minimizing the makespan/ total flowtime. Even though Lagrangian Relaxation (LR) technique is considered, in general, as a good method to obtain a lower bound, research in this direction with respect to our problem under study appears scarce. We address this gap by developing two MILP based Lagrangian Relaxation models, namely, Lagrangian Relaxation Method 1 (called Proposed Lagrangian Lower Bound Program (PLLBP) and Extended PLLBP (called Ext-PLLBP)) and Alternate Lagrangian Relaxation Method 1 (called ALR) to find the optimal solution or a lower bound on the makespan. Basically, we develop these LR methods to overcome the possible limitation of the general LR procedure involving the sub-gradient approach. Benchmark PFS problem instances are used to evaluate the performance of these methods. It is observed that the PLLBP outperforms the ALR, and it provides better lower bounds than the lower bounds (in most instances) reported in the literature. Even though the PLLBP is superior in terms of solution quality, it has a limitation that it cannot execute problem instances beyond 500 jobs due to the associated computational effort. Hence, we have next focused on developing algorithms, exploiting Assignment based Mathematical Programming Model in polynomial time, to obtain lower bounds on makespan/ total flowtime for the N-job M-machine PFS problems. The major advantage of our proposed polynomial-time algorithm is that it is a generic procedure suitable for any desired objective; also, the algorithm is computationally faster and can solve problems of any size.