Full-text resources of CEJSH and other databases are now available in the new Library of Science.
Visit https://bibliotekanauki.pl

PL EN


2011 | 3 | 2 | 7-26

Article title

Genetic Algorithms for Solving Scheduling Problems in Manufacturing Systems

Title variants

Languages of publication

EN

Abstracts

EN
Scheduling manufacturing operations is a complicated decision making process. From the computational point of view, the scheduling problem is one of the most notoriously intractable NP-hard optimization problems. When the manufacturing system is not too large, the traditional methods for solving scheduling problem proposed in the literature are able to obtain the optimal solution within reasonable time. But its implementation would not be easy with conventional information systems. Therefore, many researchers have proposed methods with genetic algorithms to support scheduling in the manufacturing system. The genetic algorithm belongs to the category of artificial intelligence. It is a very effective algorithm to search for optimal or near-optimal solutions for an optimization problem. This paper contains a survey of recent developments in building genetic algorithms for the advanced scheduling. In addition, the author proposes a new approach to the distributed scheduling in industrial clusters which uses a modified genetic algorithm.

Publisher

Year

Volume

3

Issue

2

Pages

7-26

Physical description

Dates

published
2011-01-01
online
2012-03-20

Contributors

  • Faculty of Management, Warsaw University of Technology, Warsaw, Poland

References

  • Allahverdi A., Ng C. T., Cheng T. C. E., Kovalyov M. Y. - A survey of scheduling problems with setup times or costs [in] European Journal of Operational Research, Vol. 187, 2008, pp. 985-1032.
  • Arroyo J. E. C., Armentano V. A. - Genetic local search for multi-objective flow shop scheduling problems [in] European Journal of Operational Research, Vol. 167, 2005, pp. 717-738.
  • Balin S. - Non-identical parallel machine scheduling using genetic algorithm [in] Expert Systems with Applications, Vol. 38, 2011, pp. 6814-6821.[Crossref]
  • Blanco A., Delgado M., Pegalajar M. C. - A real-coded genetic algorithm for training recurrent neural networks [in] Neural Networks, Vol. 14, 2001, pp. 93-105.[Crossref]
  • Braglia M., Grassi A. - A new heuristic for the flow-shop scheduling problem to minimize makespan and maximum tardiness [in] International Journal of Production Research, Vol. 47, No. 1, 2009, pp. 273-288.[Crossref]
  • Carlos A., Coello C. - Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art [in] Computer Methods in Applied Mechanics Engineering, Vol. 191, 2002, pp. 1245-1287.
  • Chan F. T. S., Chung S. H., Chan P. L. Y. - An adaptive genetic algorithm with dominated genes for distributed scheduling problems [in] Expert System with Applications, Vol. 29, 2005, pp. 364-371.
  • Chan F. T. S., Chung S. H., Chan L. Y. - An introduction of dominant genes in genetic algorithm for FMS [in] International Journal of Production Research, Vol. 46, No. 16, 2008, pp. 4369-4389.[Crossref]
  • Chang W. D. - Nonlinear system identification and control using a real-coded genetic algorithm [in] Applied Mathematical Modelling, Vol. 31, 2007, pp. 541-550.[Crossref]
  • Chang P. C., Chen S. H., Lin K. L. - Two-phase sub population genetic algorithm for parallel machine-scheduling problem [in] Expert Systems with Applications, Vol. 29, 2005, pp. 705-712.[Crossref]
  • Chen K. J., Ji P. - A genetic algorithm for dynamic advanced planning and scheduling (DAPS) with frozen interval [in] Expert Systems with Applications, Vol. 33, 2007, pp. 1004-1010.[Crossref]
  • Chen J. S., Pan J. C. H., Lin C. M. - A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem [in] Expert Systems with Applications, Vol. 34, Chiang 2008, pp. 570-577.[Crossref]
  • Cheng R., Gen M., Tsujimura Y. - A tutorial survey of job-shop scheduling problems using genetic algorithms. Part 1. Representation [in] Computers and Industrial Engineering, Vol. 30, No. 4, 1996, pp. 983-997.[Crossref]
  • Cheng R., Gen M., Tsujimura Y. - A tutorial survey of job-shop scheduling problems using genetic algorithms. Part II: Hybrid genetic search strategies [in] Computers and Industrial Engineering, Vol. 36, 1999, pp. 343-364.[Crossref]
  • Chiang T. C., Cheng H. C., Fu L. C. - NNMA: An effective memetic algorithm for solving multiobjective permutation flow shop scheduling problems [in] Expert Systems with Applications, Vol. 38, 2011, pp. 5986-5999.[Crossref]
  • Chung S. H., Lau H. C. W., Choy K. L., Ho G. T. S., Tse Y. K. - Application of genetic approach for advanced planning in multi-factory environment [in] International Journal of Production Economics, Vol. 127, 2010, pp. 300-308.[Crossref]
  • Davis L. - Applying adaptive algorithms to epistatic domains [at] The International Joint Conference on Artificial Intelligence, 1985, pp. 162-164.
  • França P. M., Gupta J. N. D., Mendes A. S., Moscato P., Veltink K. J. - Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups [in] Computers & Industrial Engineering, Vol. 48, 2005, pp. 491-506.[Crossref]
  • Gao J., Gen M., Sun L., Zhao X. - A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems [in] Computers & Industrial Engineering, Vol. 53, 2007, pp. 149-162.[Crossref]
  • Gao J., He G., Wang Y. - A new parallel genetic algorithm for solving multiobjective scheduling problems subjected to special process constraint [in] The International Journal of Advanced Manufacturing Technology, Vol. 43, 2009, pp.151-160.[Crossref]
  • Gao, J., Sun L., Gen M. - A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems [in] Computers & Operations Research, Vol. 35, No. 9, 2008, pp. 2892-2907.[Crossref]
  • Gao L., Zhang G., Zhang L., Li X. - An efficient memetic algorithm for solving the job shop scheduling problem [in] Computers & Industrial Engineering, Vol. 60, 2011, pp. 699-705.[Crossref]
  • Gholami M., Zandieh M. - Integrating simulation and genetic algorithm to schedule a dynamic flexible job shop [in] Journal of Intelligent Manufacturing, Vol. 20, 2009, pp. 481-498.[Crossref]
  • Goldberg D., Lingle R. - Alleles, loci and the traveling salesman problem [at] The First International Conference on Genetic Algorithms, Hillsdale 1985, pp. 154-159.
  • Goldberg D. E. - Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading, MA, 1989.
  • Guang Y., Hong Z. W. - Optimization of tool change timing in a nut forming process using genetic algorithms [in] Journal of Intelligent Manufacturing, Vol. 15, 2004, pp. 693-699.[Crossref]
  • Jarboui B., Ibrahim S., Siarry P., Rebai A. - A combinatorial particle swarm optimization for solving permutation flowshop problems [in] Computers & Industrial Engineering, Vol. 54, 2008, pp. 526-538.[Crossref]
  • Jia H. Z., Fuh J. Y. H., Nee A. Y. C., Zhang Y. F. - Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems [in] Computers & Industrial Engineering, Vol. 53, 2007, pp. 313-320.[Crossref]
  • Jolai F., Amalnick M. S., Alinaghian M., Shakhsi-Niaei M., Omrani H. - A hybrid memetic algorithm for maximizing the weighted number of just-in-time jobs on unrelated parallel machines [in] Journal of Intelligent Manufacturing, Vol. 22, 2011, pp. 247-261.[Crossref]
  • Kim K., Jeong I. J. - Flow shop scheduling with no-wait flexible lot streaming using an adaptive genetic algorithm [in] The International Journal of Advanced Manufacturing Technology, Vol. 44, 2009, pp. 1181-1190.[Crossref]
  • Kobbacy K. A. H., Vadera S., Rasmy M. H. - AI and OR in management of operations: history and trends [in] Journal of the Operational Research Society, Vol. 58, No. 1, 2007, pp. 10-28.[Crossref]
  • Liaw C. F. - A hybrid genetic algorithm for the open shop scheduling problem [in] European Journal of Operational Research, Vol. 124, 2000, pp. 28-42.[Crossref]
  • Lee Y. H., Jeong Ch. S., Moon Ch. Advanced planning and scheduling with outsourcing in manufacturing supply chain [in] Computers & Industrial Engineering, Vol. 43, 2002, pp. 351-374.[Crossref]
  • Liao L. M., Tsai C. H. - Heuristic algorithms for two-machine flow shop with availability constraints [in] Computers & Industrial Engineering, Vol. 56, 2009, pp. 306-311.[Crossref]
  • Low C., Yeh Y. - Genetic algorithm-based heuristics for an open shop scheduling problem with setup, processing, and removal times separated [in] Robotics and Computer-Integrated Manufacturing, Vol. 25, 2009, pp. 314-322.[Crossref]
  • Ławrynowicz A. - A genetic algorithm for distributed scheduling in supply networks [at] The 2nd Conference on Applied Operational Research - ICAOR'10, Turku, Finland. Lecture Notes in Management Science, Vol. 2, 2010, pp. 282-294.
  • Ławrynowicz A. - A new genetic algorithm for job shop scheduling in supply networks [at] The Fourth European Conference on Intelligent Management Systems in Operations, Greater Manchester, 2009, pp. 101-110.
  • Ławrynowicz A. - A novel intelligent method for task scheduling in industrial cluster [in] Advanced Information Technologies for Management - AITM 2009, Research Papers, No. 85, 2009, pp. 170-178.
  • Ławrynowicz A. - Integration of production planning and scheduling using an export system and a genetic algorithm [in] Journal of the Operational Research Society, Vol. 59, No. 4, 2008, pp. 455-463.[Crossref]
  • Ławrynowicz A. - Hybrid approach with an expert system and a genetic algorithm to production management in the supply net [in] Intelligent Systems in Accounting, Finance and Management, Vol. 14, No. 1-2, 2006, pp. 59-76.
  • Ławrynowicz A. - Production planning and control with outsourcing using artificial intelligence [in] International Journal Services and Operations Management, Vol. 3, No. 2, 2007, pp. 193-209.
  • Moon I., Lee S., Bae H. - Genetic algorithms for job shop scheduling problems with alternative routings [in] International Journal of Production Research, Vol. 10, 2008, pp. 2695-2705.[Crossref]
  • Mullen R. J., Monekosso D., Barman S., Remagnino P. - A review of ant algorithms [in] Expert Systems with Applications, Vol. 36, 2009, pp. 9608-9617.[Crossref]
  • Nagano M. S., Ruiz R., Lorena L. A. N. - A Constructive Genetic Algorithm for permutation flowshop scheduling [in] Computers & Industrial Engineering, Vol. 55, 2008, pp. 195-207.[Crossref]
  • Nearchou A. C. - The effect of various operators on the genetic search for large scheduling problems [in] International Journal of Production Economics, Vol. 88, 2004, pp. 191-203.[Crossref]
  • Niu K. H. - The involvement of firms in industrial clusters: A conceptual analysis [in] International Journal of Management, Vol. 26, No. 3, 2009, pp. 445-455.
  • Onwubolu G., Davendra D. - Scheduling flow shops using differential evolution algorithm [in] European Journal of Operational Research, Vol. 171, 2006, pp. 674-692.[Crossref]
  • Panahi H., Tavakkoli-Moghaddam R. - Solving a multi-objective open shop scheduling problem by a novel hybrid ant colony optimization [in] Expert Systems with Applications, Vol. 38, 2011, pp. 2817-2822.[Crossref]
  • Prakash A., Chan F. T. S., Deshmukh S. G. - FMS scheduling with knowledge based genetic algorithm approach [in] Expert Systems with Applications, Vol. 38, 2011, pp. 3161-3171.[Crossref]
  • Rajendran C., Ziegler H. - Ant-colony algorithms for permutation flow shop scheduling to minimize makespan/total flowtime of jobs [in] European Journal of Operational Research, Vol. 155, 2004, pp. 426-438.[Crossref]
  • Rajkumar R., Shahabudeen P. - An improved genetic algorithm for the flowshop scheduling problem [in] International Journal of Production Research, Vol. 47, No. 1, 2009, pp. 233-249.[Crossref]
  • Ruiz R., Maroto C. - A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility [in] European Journal of Operational Research, Vol. 169, 2006, pp. 781-800.
  • Ruiz R., Maroto C., Alcaraz J. - Two new robust genetic algorithms for the flowshop scheduling problem [in] Omega, Vol. 34, 2006, pp.461-476.[Crossref]
  • Tavakkoli-Moghaddam R., Azarkish M., Sadeghnejad-Barkousaraie A. - Solving a multi-objective job shop scheduling problem with sequence-dependent setup times by a Pareto archive PSO combined with genetic operators and VNS [in] The International Journal of Advanced Manufacturing Technology, Vol. 53, 2011, pp. 733-750.[Crossref]
  • Tseng L. Y., Lin Y. T. - A genetic local search algorithm for minimizing total flowtime in the permutation flowshop scheduling problem [in] International Journal of Production Economics, Vol. 127, 2010, pp. 121-128.[Crossref]
  • Wang Y. M., Yin H. L., Wang J. - Genetic algorithm with new encoding scheme for job shop scheduling [in] The International Journal of Advanced Manufacturing Technology, Vol. 44, 2009, pp. 977-984.[Crossref]
  • Vallada E., Ruiz R. - A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup limes [in] European Journal of Operational Research, Vol. 211, 2011, pp. 612-622.
  • Xu X., Xu Z., Gu X. - An asynchronous genetic local search algorithm for the permutation flowshop scheduling problem with total flowtime minimization [in] Expert Systems with Applications, Vol. 38, 2011, pp. 7970-7979.[Crossref]
  • Ying-Hua C., Young-Chang H. - Dynamic programming decision path encoding of genetic algorithms for production allocation problems [in] Computers & Industrial Engineering, Vol. 54, 2008, pp. 53-65.
  • Zhang G., Gao L., Shi Y. - An effective genetic algorithm for the flexible job-shop scheduling problem [in] Expert Systems with Applications, Vol. 38, 2011, pp. 3563-3573.[Crossref]
  • Zhang C., Rao Y., Li P. - An effective hybrid genetic algorithm for the job shop scheduling problem [in] The International Journal of Advanced Manufacturing Technology, Vol. 39, 2008, pp. 965-974.[Crossref]
  • Zhang R., Wu C. A. - A hybrid approach to large-scale job shop scheduling [in] Applied Intelligence, Vol. 32, 2010, pp. 47-59.[Crossref]
  • Zegordi S. H., Abadi I. N. K., Nia M. A. B. - A novel genetic algorithm for solving production and transportation scheduling in a two-stage supply chain [in] Computers & Industrial Engineering, Vol. 58, 2010, pp. 373-381.[Crossref]
  • Zobolas G. I., Tarantilis C. D., Ioannou G. - A hybrid evolutionary algorithm for the job shop scheduling problem [in] Journal of the Operational Research Society, Vol. 60, No. 2, 2009, pp. 221-235[Crossref]

Document Type

Publication order reference

Identifiers

YADDA identifier

bwmeta1.element.doi-10_2478_v10238-012-0039-2
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.