An optimization scheme for minimizing makespan of Gari processing jobs using improved initial population Genetic Algorithm (GA) is proposed. GA with initial population improved by using job sequencing and dispatching rules of First Come First Served (FCFS), Shortest Processing Time (SPT), Longest Processing Time (LPT), and Modified Johnson’s Algorithm for -machines in order to obtain better schedules than is affordable by GA with freely generated initial population and by individual traditional sequencing and dispatching rules was used. The traditional GA crossover and mutation operators as well as a custom-made remedial operator were used together with a hybrid of elitism and roulette wheel algorithms in the selection process based on job completion times. A test problem of 20 jobs with specified job processing and arrival times was simulated through the integral 5-process Gari production routine using the sequencing and dispatching rules, GA with freely generated initial population, and the improved GA. Comparisons based on performance measures such as optimal makespan, mean makespan, execution time, and solution improvement rate established the superiority of the improved initial population GA over the traditional sequencing and dispatching rules and freely generated initial population GA. 1. Introduction One of the most important products obtained from the processing of cassava is “Gari.” Gari is a creamy-white, granular flour with a slightly fermented flavor and a slightly sour taste made from fermented, gelatinized fresh cassava tubers. Gari processing industries occupy a substantial portion of small and medium enterprises (SMEs) in Nigeria. In the past few decades, research on Gari production has yielded tremendous gain particularly in the areas of developing Gari processing machine and improving on its quality. However, little or no attention has been given to scheduling of customers’ orders in a way that would improve delivery performance and inventory management and reduce production cycle times and overall cost associated with the production process. Hence, operational bottlenecks are often experienced in the day to day activities while the desire for appropriate processor becomes imperative. Job scheduling in a Gari processing firm is analogous to a flow shop in which a set of -jobs have to be processed with identical flow patterns on -machines. In their works [1–3] developed scheduling models on the following assumptions.(i)Each of the -jobs has the same ordering of machines for its process sequence.(ii)At a time, every job is processed on
References
[1]
T. Aldowaisan and A. Allahverdi, “New heuristics for no-wait flowshops to minimize makespan,” Computers and Operations Research, vol. 30, no. 8, pp. 1219–1231, 2003.
[2]
R. Bellman, “Mathematical aspects of scheduling theory,” Journal of the Society for Industrial and Applied Mathematics, vol. 4, no. 3, pp. 168–205, 1956.
[3]
M. Y. Wang, S. P. Sethi, and S. L. Van De Velde, “Minimizing makespan in a class of re-entrant shops,” Operations Research, vol. 45, no. 5, pp. 702–712, 1997.
[4]
C. H. Campbell, D. R. Dudek, and S. M. Smith, “A heuristic algorithm for n job, m machine sequencing problem,” Management Science, vol. 16, no. 10, pp. 630–637, 1970.
[5]
P.-C. Chang, S.-H. Chen, and K.-L. Lin, “Two-phase sub population genetic algorithm for parallel machine-scheduling problem,” Expert Systems with Applications, vol. 29, no. 3, pp. 705–712, 2005.
[6]
D. G. Dannenbring, “An evaluation of flow-shop sequencing heuristics,” Management Science, vol. 23, no. 11, pp. 1174–1182, 1977.
[7]
C.-L. Chen, V. S. Vempati, and N. Aljaber, “An application of genetic algorithms for flow shop problems,” European Journal of Operational Research, vol. 80, no. 2, pp. 389–396, 1995.
[8]
H. D. Pour, “A new heuristic for the n-job, m-machine flow-shop problem,” Production Planning and Control, vol. 12, no. 7, pp. 648–653, 2001.
[9]
A. Dolgui, B. Finel, N. Guschinsky, G. Levin, and F. Vernadat, “MIP approach to balancing transfer lines with blocks of parallel operations,” IIE Transactions, vol. 38, no. 10, pp. 869–882, 2006.
[10]
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, Mass, USA, 1989.
[11]
S. Reza Hejazi and S. Saghafian, “Flowshop-scheduling problems with makespan criterion: a review,” International Journal of Production Research, vol. 43, no. 14, pp. 2895–2929, 2005.
[12]
F. Werner, “On the heuristic solution of the permutation flowshop problem by path algorithms,” Computer and Operations Research, vol. 20, no. 7, pp. 707–722, 1993.
[13]
T. Stutzle, Local search algorithm for combinatorial problems: analysis, improvements, and newapplications [Ph.D. thesis], Darmstadt University of Technology, Department of Computer Science, 1998.
[14]
C. Rajendra and H. Ziegler, “Ant colony algorithms for permutationflowshop scheduling to minimize makespan/totalflow-time of jobs,” European Journal of Operational Research, vol. 155, no. 2, pp. 426–438.
[15]
J. Grabowski and M. Wodecki, “A very fast tabu search algorithmfor permutation flow shop problem with makespancriterion,” Computers and Operations Research, vol. 31, no. 11, pp. 1891–1909, 2004.
[16]
R. Ruiz and C. Maroto, “A comprehensive review and evaluationof permutation flowshop heuristics,” European Journal of Operational Research, vol. 165, no. 2, pp. 479–494, 2005.
[17]
J. Soewande, T. Octavia, and I. H. Sahputra, “Robust hybrid genetic algorithm for a flow-shop scheduling problem (A case study at PT FSCM manufacturing Indonesia),” Jurnal of Teknik Industri, vol. 9, no. 2, pp. 144–151, 2008.
[18]
M. S. Nagano, R. Ruiz, and L. A. N. Loren, “A constructive genetic algorithm for permutation flow shop scheduling,” Computer and Industrial Engineering, vol. 55, no. 1, pp. 195–207, 2008.
[19]
R. Ruiz, J. C. Garcia-Diaz, and C. Maroto, “Considering schedulling and preventive maintenance in the flow shop sequencing problem,” Computer and Operations Research, vol. 34, no. 11, pp. 3314–3330, 2007.
[20]
A. El-Bouri, N. Azizi, and S. A. Zolfaghari, “Comparative study of a new heuristic based on adaptive memory programming and simulated annealing: the case of job shop scheduling,” European Journal of Operational Research, vol. 177, no. 3, pp. 1894–1910, 2007.
[21]
J. H. Holland, Adaptation in Natural and Artificial Systems: An IntroducTory Analysis with Applications to Biology, Control and Artificial Intelligence, University of Michigan Press, 1975.
[22]
J. C.-H. Pan and J.-S. Chen, “Minimizing makespan in re-entrant permutation flow-shops,” Journal of the Operational Research Society, vol. 54, no. 6, pp. 642–653, 2003.
[23]
J. C. H. Pan and J. S. Chen, “A comparative study of schedule-generation procedures for the re-entrant shops,” International Journal of Industrial Engineering, vol. 11, no. 4, pp. 313–321, 2004.
[24]
M. Pinedo, Scheduling Theory, Algorithms and Systems, Prentice Hall, Englewood Cliffs, NJ, USA, 2nd edition, 2002.
[25]
S. G. Ponnambalam, P. Aravindan, and S. Chandrasekaran, “Constructive and improvement flow shop scheduling heuristics: an extensive evaluation,” Production Planning and Control, vol. 12, no. 4, pp. 335–344, 2001.
