Forward Shift Heuristic for Minimization of Number of Early-Tardy Jobs in Just-In-Time Scheduling in a Flow Shop with Distinct Due Windows


Authors : Idowu, A. Gbolahan; Adamu, O. Muminu; Mustapha, A. Rilwan; Sawyerr, A. Babatunde; Rahman, O. Idris

Volume/Issue : Volume 7 - 2022, Issue 3 - March

Google Scholar : https://bit.ly/3IIfn9N

Scribd : https://bit.ly/3RxJ9Dw

DOI : https://doi.org/10.5281/zenodo.6827336

Abstract : This paper addresses the problem of scheduling production to meet Just-in-Time requirement in a Flow Shop where jobs are to be completed withingiven due windows rather than single due dates. This problem has been proven to be NP-Complete in the strong sense and shown to be intractable as the number of jobs-andmachines combination increase. Consequently, a Forward Shift Search (FSS) algorithm is developed to solve large problem instances. To assess the performance of FSS, a benchmark of 1200 test problem were solved and compared with solution obtained by an exiting algorithm in the literature. FSS performs better in terms of quality of solution and computational time. Also, FSS obtained a relative deviation index of 4% when compared with a optimal solution obtained by a commercial solver within 600 seconds of computational time. Therefore, FSS can be deployed to obtain good approximation schedule for large scale production where desired error tolerance is not more than 0.004.

Keywords : Early/Tardy, Forward-Shift,Flow Shop, Heuristics, Just-In-Time

This paper addresses the problem of scheduling production to meet Just-in-Time requirement in a Flow Shop where jobs are to be completed withingiven due windows rather than single due dates. This problem has been proven to be NP-Complete in the strong sense and shown to be intractable as the number of jobs-andmachines combination increase. Consequently, a Forward Shift Search (FSS) algorithm is developed to solve large problem instances. To assess the performance of FSS, a benchmark of 1200 test problem were solved and compared with solution obtained by an exiting algorithm in the literature. FSS performs better in terms of quality of solution and computational time. Also, FSS obtained a relative deviation index of 4% when compared with a optimal solution obtained by a commercial solver within 600 seconds of computational time. Therefore, FSS can be deployed to obtain good approximation schedule for large scale production where desired error tolerance is not more than 0.004.

Keywords : Early/Tardy, Forward-Shift,Flow Shop, Heuristics, Just-In-Time

Never miss an update from Papermashup

Get notified about the latest tutorials and downloads.

Subscribe by Email

Get alerts directly into your inbox after each post and stay updated.
Subscribe
OR

Subscribe by RSS

Add our RSS to your feedreader to get regular updates from us.
Subscribe