PRODUCTION SCHEDULING PROBLEM SOLVING USING GENETIC AND GREEDY ALGORITHMS WITH SEQUENCE- DEPENDENT SET-UP TIMES
Keywords:
Production Scheduling, Set-up Time, Genetic algorithm , Greedy algorithmAbstract
In today’s competitive markets, the importance of good scheduling strategies in manufacturing companies, lead to the need of developing efficient methods to solve complex scheduling problems. In scheduling attempt to fill the gap between scheduling theory and scheduling practice, with the aim to give answer to respond to market demand for more efficient method to solve complex scheduling problems. Although classical scheduling theory are one of the most studied field in Operations Research, some practical environments are often ignored in the classical models, since they improve the complexity of mathematical models. For discussion in the gap between scheduling theory and scheduling practice Main aim of this research work is to solve two production scheduling problems with sequence dependent setup times. The setup times are one of the most common complications in scheduling problems, and are usually associated with cleaning operations and changing tools and shapes in machines. The first problem considered is a single machine scheduling with release dates, sequence dependent setup times and delivery times. The performances measure is the maximum lateness. The second problem is a job shop scheduling problem with sequence dependent setup times where the objective is to minimize the make span. These two problems were addressed using genetic and greedy algorithm. There by, a highly efficient decoding procedure is proposed which strongly improves the quality of schedules. We present several priority dispatching rules for both problems, followed by a study of their performance.
Downloads
References
Adams J Balas E and Zawack D (1988), “The Shifting Bottleneck Procedure for Job Shop Scheduling”, Management Science, Vol. 34(3), 391-401.
Barman S (1997), “Simple priority rule combinations: an approach to improve both flow time and tardiness”, International Journal of Production Research, Vol.35 (10), 2857-2870.
Beasley J E (1990), OR-Library: “Distributing Test Problems by Electronic Mail”, Journal of the Operational Research Society, Vol. 41(11), 1069-1072.
Bratley P Fox B L and Schrage L E (1983), “A guide to Simulation”, New York: Springer- Verlag.
Bruno J and Downey P (1978), “Complexity of Task Sequencing With Deadlines”, Setup Times and Changeover Costs. SIAM Journal of Computing, Vol.7, 393-404.
Carlier J (1982), “The one-machine sequencing problem”, European Journal of Operational Research,Vol. 11, 42-47.
Conway R W Maxwell W L and Miller L W (1967), “Theory of Scheduling”, eading, Massachussets: Addison-Wesley.
Fisher H and Thompson G L (1963), “Probabilistic learning combinations of local job-shop scheduling rules”, Industrial Scheduling. (Englewood Cliffs, New Jersey: Prentice Hall: 225-251).
Garey M R and Johnson D S (1979), “Computers and Intractability: A Guide to the Theory of NP-ompleteness”, San Francisco: Freeman.
Grabowski J E Nowicki E and Zdrzalka S (1986), “A block approach for single machine scheduling with release dates and due dates”, European Journal of Operational Research, Vol. 26, 278-285.
Gupta J N D (1988), “Single facility scheduling with multiple job classe”,. European journal Operations Research, Vol.8, 42-45.
Hoogeveen J A Lenstra J K and van de Velde S L (1997), “Sequencing and scheduling: an annotated bibliography, Memorandum COSOR 97-02”, Eindhoven University of Technoloy, Eindhoven, The Nederlands.
Ríos R and Bard J (1997), “A branch-and-bound algorithm for flowshop scheduling with setup times”, Technical Report ORP97-02, University of Texas, Austin.
Schrage L (1971), “Obtaining optimal solutions to resource constrained network scheduling problem”, unpublished manuscript.
Storer R H Wu S D and Vaccari R (1992), “New search spaces for sequencing instances with application to job-shop scheduling”, Management Science, Vol. 38, 1495-1509.
Taillard E (1993), “Benchmarks for basic scheduling problems”, European Journal of Operational Research,Vol. 64, 278-285.
Williams D and Wirth A (1996), “A New Heuristic for a Single Machine Scheduling Problem with Setup Times”, Journal of the Operations Research Society, Vol. 47, 175-180.
Florentina Alina Chircu (2010), Using Genetic Algorithms for Production Scheduling, Petroleum-Gas University of Ploiesti, Informatics Department, Ploieşti, Romania.
Ashwani Dhingra, Pankaj Chandna, Hybrid Genetic Algorithm for Multicriteria Scheduling with Sequence Dependent Set up Time, Haryana,India.
João António Noivoa and Helena Ramalhinho-Lourençob, Solving two production scheduling problems with sequence-dependent set-up times, Departamento de Electrónica Industrial, Universidade do Minho, Campus de Azurém, 4800Guimarães, Portugal.
Man K F Tang K S and Kwong S (1996), Member IEEE, Genetic Algorithms: Concepts and Applications.
Falkenauer E and Bouffouix S, “A Genetic Algorithm for Job Shop”, CRIF - Research Center for Belgian Metalworking Industry, Brussels, Belgium.
Ruben Ruiz Thomas St Äutzley, “An Iterated Greedy Algorithm for the Flowshop Problem with Sequence Dependent Setup Times”, Valencia, Spain.
Avi Dechter and Rina Dechter (1989), “On the Greedy solution of Ordering Problems”, CA.
Naderi B and Rubén Ruiz, “The distributed permutation flowshop scheduling problem”
