A heuristic algorithm for scheduling in a flow shop environment to minimize makespan
Scheduling ‘n’ jobs on ‘m’ machines in a flow shop is NP- hard problem and places itself at prominent place in the area of production scheduling. The essence of any scheduling algorithm is to minimize the makespan in a flowshop environment. In this paper an attempt has been made to develop a heurist...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Growing Science
2015-04-01
|
| Series: | International Journal of Industrial Engineering Computations |
| Subjects: | |
| Online Access: | http://www.growingscience.com/ijiec/Vol6/IJIEC_2014_43.pdf |
| _version_ | 1818194470932316160 |
|---|---|
| author | Arun Gupta Sant Ram Chauhan |
| author_facet | Arun Gupta Sant Ram Chauhan |
| author_sort | Arun Gupta |
| collection | DOAJ |
| description | Scheduling ‘n’ jobs on ‘m’ machines in a flow shop is NP- hard problem and places itself at prominent place in the area of production scheduling. The essence of any scheduling algorithm is to minimize the makespan in a flowshop environment. In this paper an attempt has been made to develop a heuristic algorithm, based on the reduced weightage of ma-chines at each stage to generate different combination of ‘m-1’ sequences. The proposed heuristic has been tested on several benchmark problems of Taillard (1993) [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278-285.]. The performance of the proposed heuristic is compared with three well-known heuristics, namely Palmer’s heuristic, Campbell’s CDS heuristic, and Dannenbring’s rapid access heuristic. Results are evaluated with the best-known upper-bound solutions and found better than the above three. |
| first_indexed | 2024-12-12T01:02:49Z |
| format | Article |
| id | doaj.art-b9daad5ced3b458b9d6667a7a81f165f |
| institution | Directory Open Access Journal |
| issn | 1923-2926 1923-2934 |
| language | English |
| last_indexed | 2024-12-12T01:02:49Z |
| publishDate | 2015-04-01 |
| publisher | Growing Science |
| record_format | Article |
| series | International Journal of Industrial Engineering Computations |
| spelling | doaj.art-b9daad5ced3b458b9d6667a7a81f165f2022-12-22T00:43:40ZengGrowing ScienceInternational Journal of Industrial Engineering Computations1923-29261923-29342015-04-016217318410.5267/j.ijiec.2014.12.002A heuristic algorithm for scheduling in a flow shop environment to minimize makespanArun Gupta Sant Ram Chauhan Scheduling ‘n’ jobs on ‘m’ machines in a flow shop is NP- hard problem and places itself at prominent place in the area of production scheduling. The essence of any scheduling algorithm is to minimize the makespan in a flowshop environment. In this paper an attempt has been made to develop a heuristic algorithm, based on the reduced weightage of ma-chines at each stage to generate different combination of ‘m-1’ sequences. The proposed heuristic has been tested on several benchmark problems of Taillard (1993) [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278-285.]. The performance of the proposed heuristic is compared with three well-known heuristics, namely Palmer’s heuristic, Campbell’s CDS heuristic, and Dannenbring’s rapid access heuristic. Results are evaluated with the best-known upper-bound solutions and found better than the above three.http://www.growingscience.com/ijiec/Vol6/IJIEC_2014_43.pdfFlow-shopHeuristicsMakespanSchedulingBenchmark Problems |
| spellingShingle | Arun Gupta Sant Ram Chauhan A heuristic algorithm for scheduling in a flow shop environment to minimize makespan International Journal of Industrial Engineering Computations Flow-shop Heuristics Makespan Scheduling Benchmark Problems |
| title | A heuristic algorithm for scheduling in a flow shop environment to minimize makespan |
| title_full | A heuristic algorithm for scheduling in a flow shop environment to minimize makespan |
| title_fullStr | A heuristic algorithm for scheduling in a flow shop environment to minimize makespan |
| title_full_unstemmed | A heuristic algorithm for scheduling in a flow shop environment to minimize makespan |
| title_short | A heuristic algorithm for scheduling in a flow shop environment to minimize makespan |
| title_sort | heuristic algorithm for scheduling in a flow shop environment to minimize makespan |
| topic | Flow-shop Heuristics Makespan Scheduling Benchmark Problems |
| url | http://www.growingscience.com/ijiec/Vol6/IJIEC_2014_43.pdf |
| work_keys_str_mv | AT arungupta aheuristicalgorithmforschedulinginaflowshopenvironmenttominimizemakespan AT santramchauhan aheuristicalgorithmforschedulinginaflowshopenvironmenttominimizemakespan AT arungupta heuristicalgorithmforschedulinginaflowshopenvironmenttominimizemakespan AT santramchauhan heuristicalgorithmforschedulinginaflowshopenvironmenttominimizemakespan |