The Comparison of the Integer Programming Models for Solving the Stage Shop Scheduling Problem

Document Type : Research Paper

Author

Abstract

The development and extending the classic models for approaching the real world conditions are always in consideration of researchers. For this reason, many efforts are made for generalization of the job shop scheduling problem. The stage shop scheduling problem is defined as a generalization of the mixed shop and a special case of the general shop. In a stage shop, each job includes several stages and each stage contains one or more operations. A stage is a subset of the set of the operations of a job so that these operations can be processed in any arbitrary order. In other words, the process of the operations of a stage cannot be initiated unless all the operations of the previous stage are completed. In this paper, two mixed integer programming models are presented for each of the problems "the stage shop scheduling with total weighted tardiness criterion" and "the stage shop scheduling with makespan criterion" (totally four models) and then the models are compared. For the comparison of the efficiency of the proposed models, some problem instances are generated. The computational results show that the second model is more efficient.

Keywords

References

1.         Nasiri, M.M., F. Kianfar. (2012). “A guided tabu search/path relinking algorithm for the job shop problem”. The International Journal of Advanced Manufacturing Technology, Vol.58, pp. 1105-1113.
2.         Nasiri, M.M., F. Kianfar. (2012). “A GES/TS algorithm for the job shop scheduling”. Computers & Industrial Engineering, Vol.62, pp. 946-952.
3.         Beck, J.C., T. Feng, J.-P. Watson. (2011). “Combining constraint programming and local search for job-shop scheduling”. INFORMS Journal on Computing, Vol.23, pp. 1-14.
4.         Amin-Naseri, M.R., M.A. Beheshti-Nia. (2009). “Hybrid flow shop scheduling with parallel batching”. International Journal of Production Economics, Vol.117, pp. 185-196.
5.         Shakhlevich, N.V., Y.N. Sotskov, F. Werner. (2000). “Complexity of mixed shop scheduling problems: A survey”. European Journal of Operational Research, Vol.120, pp. 343-351.
6.         Nasiri, M.M., F. Kianfar. (2011). “A GA/TS algorithm for the stage shop scheduling problem”. Computers & Industrial Engineering, Vol.61, pp. 161-170.
7.         Carlier, J., E. Pinson. (1989). “An algorithm for solving the job-shop problem”. Management science, Vol.35, pp. 164-176.
8.         Lawrence, S. (1984). “Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement)”. Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania,
9.         Essafi, I., Y. Mati, S. Dauzère-Pérès. (2008). “A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem”. Computers & Operations Research, Vol.35, pp. 2599-2616.
 
 
 
Journal of Modeling in Engineering
Volume 16, Issue 53
July 2018
Pages 379-387

Files

History

  • Receive Date: 05 February 2014
  • Revise Date: 04 February 2017
  • Accept Date: 22 August 2017

Share

How to cite

Statistics