Permutation flowshop scheduling to obtain the optimal solution/a lower bound with the makespan objective
- PDF / 374,758 Bytes
- 19 Pages / 595.276 x 790.866 pts Page_size
- 76 Downloads / 213 Views
Sådhanå (2020)45:228 https://doi.org/10.1007/s12046-020-01444-9
Sadhana(0123456789().,-volV)FT3](012345 6789().,-volV)
Permutation flowshop scheduling to obtain the optimal solution/a lower bound with the makespan objective THAMARASSERY ABDULJALEEL JESSIN1,2, SAKTHIVEL MADANKUMAR3 and CHANDRASEKHARAN RAJENDRAN1,* 1
Department of Management Studies, Indian Institute of Technology Madras, Chennai 600036, India TKM College of Engineering, Kollam 691005, India 3 Trimble Information Technologies India Private Limited, Chennai 600113, India e-mail: [email protected]; [email protected]; [email protected] 2
MS received 24 January 2020; revised 25 April 2020; accepted 3 June 2020 Abstract. This paper 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 using Lagrangian Relaxation (LR) technique. Even though 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 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 in that it cannot execute problem instances beyond 500 jobs due to the associated computational effort. Keywords. Manufacturing; permutation flowshop scheduling; makespan; mixed integer linear programming model; lower bound; Lagrangian relaxation.
1. Introduction A flowshop is a conventional manufacturing system where all jobs are processed on all machines with the same sequence of operations on machines. The Permutation Flowshop Problem (PFS) is a special case of the flowshop problem where we schedule a set of N jobs non-preemptively on M machines in the same order on every machine. Since the publication of Johnson’s seminal paper [1], the PFS problem has become a topic of interest for researchers. Among the performance measures, the minimization of makespan is the widely studied objective due to the implication that the minimization of makespan leads to the reduction in idle times of machines, especially the minimum idle time of the last machine and the production run length. The problem is denoted by FjprmujCmax (see Pinedo [2]). It is well known for the two-machine flowshop problem with the consideration of the makespan objective, Johnson’s
Data Loading...
