Showing 3 results for Makespan
Nasim Nahavandi, Ebrahim Asadi Gangraj,
Volume 25, Issue 1 (2-2014)
Abstract
Flexible flow shop scheduling problem (FFS) with unrelated parallel machines contains sequencing in flow shop where, at any stage, there exists one or more processors. The objective consists of minimizing the maximum completion time. Because of NP-completeness of FFS problem, it is necessary to use heuristics method to address problems of moderate to large scale problem. Therefore, for assessment the quality of this heuristic, this paper develop a global lower bound on FFS makespan problems with unrelated parallel machines.
Ebrahim Asadi Gangraj,
Volume 28, Issue 1 (3-2017)
Abstract
In hybrid flow shop scheduling problem (HFS) with unrelated parallel machines, a set of n jobs are processed on k machines. A mixed integer linear programming (MILP) model for the HFS scheduling problems with unrelated parallel machines has been proposed to minimize the maximum completion time (makespan). Since the problem is shown to be NP-complete, it is necessary to use heuristic methods to tackle the moderate to large scale problems. This article presents a new bottleneck-based heuristic to solve the problem. To improve the performance of the heuristic method, a local search approach is embedded in the structure of the heuristic method. To evaluate the performance of the proposed heuristic method, a new lower bound is developed based on Kurz and Askin [1] lower bound. For evaluation purposes, two series of test problems, small and large size problems, are generated under different production scenarios. The empirical results show that average difference between lower bound and optimal solution as well as lower bound and heuristic method are equal to 2.56% and 5.23%, respectively. For more investigation, the proposed heuristic method is compared by other well-known heuristics in the literature. The results verify the efficiency of the proposed heuristic method in term of number of best solution.
Prasad Bari, Prasad Karande,
Volume 34, Issue 2 (6-2023)
Abstract
This paper presents a model for minimizing the makespan in the flow shop scheduling problem. Due to the impact of increased workloads, flow shops are becoming more popular and widely used in industries. To solve the challenge of minimizing makespan, a Hybrid-Heuristic-Metaheuristic-Genetic-Algorithm (HHMGA) is proposed. The proposed HHMGA algorithm is tested using the simulation software and demonstrated with steel industry data. The results are compared with those of the best available flow shop problem algorithms such as Palmer’s slope index, Campbell-Dudek-Smith (CDS), Nawaz-Enscore-Ham (NEH), genetic algorithm (GA) and particle swarm optimization (PSO). According to empirical results and relative differences from the lower bound, the proposed technique outperforms the three heuristics and two metaheuristics algorithms in three of six cases, while the remaining three produce the same results as the NEH heuristic. In comparison to the steel industry's regular job scheduling technique, the simulation model based on HHMGA can save 4642 hours. It was discovered that the suggested model enhanced the job sequence based on the makespan requirements.
