A lower bound for job shop scheduling problem with a parallel assembly stage by graph coloring approach

Document Type : Research Paper

Authors

Abstract

Abstract: Scheduling is one of the most applicable problems in industry that is considerably studied by researchers in the recent years. It is necessary to extend the models that can be applied in real situations. To this end researchers have tried to consider assembly and processing stages simultaneously. In this research according to the importance of different production stages in industry, and also to consider problem in real situation, job shop scheduling problem by considering a parallel assembly stage is studied to minimize completion time for all products. At first, this problem is reduced to graph coloring. Because this problem and graph coloring problem are NP-hard, a hybrid Genetic-Particle swarm optimization algorithm for medium and large size problems used. So in this research a lower bound for this problem based on graph coloring problem is proposed to evaluate the efficiency and effectiveness of the proposed algorithm.

Keywords: Scheduling, Job shop, Parallel Assembly, Graph Coloring

Keywords

Main Subjects

References

  1. Lee, C. Y., Cheng, T. C. E. and Lin, B. M. T. (1993). “Minimizing the Makespan in the-Machine Assembly-Type Flowshop Scheduling Problem”, Management Science, Vol. 39, No. 5, PP. 616-625.
  2. Al Anzi, F. S., and Allahverdi, A. (2013). “An Artificial Immune System Heuristic for Two-Stage Multi-Machine Assembly Scheduling Problem to Minimize Total Completion Time”, Journal of Manufacturing Systems, Vol. 32, No. 4, PP. 825– 830.
  3. Allahverdi, A., and Al Anzi, F. S. (2006). “A Branch and Bound Algorithm for Three-Machine Flowshop Scheduling Problem to Minimize Total Completion Time with Separate Setup Times”, European Journal of Operational Research, Vol. 169, No. 3, PP. 767-780.
  4. Seyedi, I., Maleki Daronkolaei, A., and Kalashi, F. (2012). “Tabu Search and Simulated Annealing for New Three-Stage Assembly Flow Shop Scheduling with Blocking”, Interdisciplinary Journal of Contemporary Research in usiness, Vol. 4, No. 8, PP. 394-402.
  5. Navaei, J. et al. (2014). “Heuristics for an Assembly Flow Shop with Non-Identical Assembly Machines and Sequence Dependent Setup Times to Minimize Sum of Holding and Delay Costs”, Computers and Operations Research, Vol. 44, No. 4, PP. 52–65.
  6. Hariri, A. M. A., and Potts, C. N. (1997). “A Branch and Bound Algorithm for the Two-Stage Assembly Scheduling Problem”, European Journal of Operational Research, Vol. 103. No. 3, PP. 547-556.
  7. Yokoyama, M. (2001). “Hybrid Flow Shop Scheduling with Assembly Operations”, International Journal of Production Economics,Vol. 73, PP. 103-116.
  8. Sung, Ch.S., and Juhn, J. (2009). “Makespan Minimization for a 2-Stage Assembly Scheduling Problem Subject to Component Available Time Constraint”, International Journal of Production Economics,Vol. 119, No. 2, PP. 392-401.
  9. Sung, C. S., and Kim, H. Ah. (2008). “A Two-Stage Multiple-Machine Assembly Scheduling Problem for Minimizing Sum of Completion Times”, International Journal of Production Economics,Vol. 113, No. 2, PP. 1038-1048.
  10. Fattahi, P., Hosseini, S. M. H., and Jolai, F. (2012). “A Mathematical Model and Extension Algorithm for Assembly Flexible Flow Shop Scheduling Problem”, International Journal of Advance Manufacture Technology, Vol. 65, No. 5-8, PP. 787-802.
  11. Garey, M. R., and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, LA: Freeman.
  12. Sotskov, Y. N., and Tanaev, V. S. (1976). “Chromatic Polynomial of a Mixed Graph”, Vestsi Akademii Navuk BSSR, Seryya Fizika-Matematychnykh Navuk, Minsk. Vol. 140, No. 6, PP. 20–23. Russian.
  13. Sotskov, Y. N., Dolgui, A., and Werner, F. (2001). “Mixed graph coloring for unit-time job-shop scheduling”, International Journal of Mathematical Algorithms, Vol. 2, No. 4, PP. 289–‌323.
  14. Al Anzi, F. S. et al. (2006). “Using Mixed Graph Coloring to Minimize Total Completion Time in Job Shop Scheduling”, applied Mathematics and omputation, Vol. 182, No. 2, PP. 1137–1148.
  15. Kouider, A. et al. (2015). “Mixed Integer Linear Programs and Tabu Search Approach to Solvemixed Graph Coloring for Unit-Time Job Shop Scheduling”, In IEEE International Conference on Automation Science and Engineering (CASE), August 24–28, Gothenburg, Sweden, 1177–1181.
  16. Kouider, A. et al. (2017). “Mixed Graph Colouring For Unit-Time Scheduling”, International Journal of Production Research,Vol. 55, No. 6, PP. 1720-1729.
  17. Shen, J. W. (2003). “Solving the Graph Coloring Problem Using Genetic Programming”, In Genetic Algorithms and Genetic Programming at Stanford 2003: 187-196, Stanford Bookstore.
  18. Daneshamooz, F., Jabbari, M., and Fattahi, P. (2013). “A Model for Jobshop Scheduling with a Parallel Assembly Stage to Minimize Makespan”, Journal of Industrial Engineering Research in Production Systems,Vol. 2, No. 4, PP. 39-53.
  19. Setak, M. et al. (2014). “Capacitated Multi-Depot Vehicle Routing Problem with Inter-Depot Routes”, Journal of Industrial Engineering, University of Tehran, Special Issue, Vol. 48, PP. 11-18.
  20. Kao, Y. T., and Zahara, E. (2008). “A Hybrid Genetic Algorithm and Particle Swarm Optimization for Multimodal Functions”, Applied Soft Computing, Vol. 8, No. 2, PP. 849-857.
  21. Eberhart, R., and Kennedy, J. (1995). “A New Optimizer Using Particle Swarm Theory”, 6th Int. Symposium on Micro Machine and Human Science, Nagoya, Japan, PP. 4-39.
  22. Kiani, M. et al. (2015). “An Efficient Genetic Algorithm for a Vehicle Routing Problem Considering the Competency of Working Teams”, Journal of Industrial Engineering, University of Tehran, Vol. 49, No. 2, PP. 257-271.
Advances in Industrial Engineering
Volume 52, Issue 3
October 2018
Pages 367-378

Files

Share

How to cite

Statistics