AASCIT - Journal - All Issues

American Journal of Mathematical and Computational Sciences

The Journal

Indexing

Manuscript Information

Mixed Integer Programming for Job Shop Scheduling Problem with Separable Sequence-Dependent Setup Times

American Journal of Mathematical and Computational Sciences
Vol.3 , No. 1, Publication Date: Jan. 20, 2018, Page: 31-36

1064 Views Since January 20, 2018, 1321 Downloads Since Jan. 20, 2018

Paper in PDF (458K)

Follow on

Authors

[1]	Emna Driss, Nord American University, International Institute of Technology, Sfax, Tunisia.
[2]	Racem Mallouli, Umm Al-Qura University, Al-Qunfudhah Engineering College, Khalidiah, Saudi Arabia.
[3]	Wafik Hachicha, University of Sfax, Higher Institute of Management of Sfax, Sfax, Tunisia.

Abstract

In scheduling practice, the setup times are often important and no one can neglect them. That is why many research studies which deal with job shop problems (JSP) with separable sequence-dependent setup times (SDST) have been developed according to various objectives and hypotheses. Several complex programming formulations are proposed in the literature in order to minimize the makespan. Because of this complexity, there are few studies using exact approaches and the current trend is towards heuristics and metaheuristic based-methodologies. Therefore, it would be useful to develop a new model solvable by any optimizer directly. In this context, a new mixed integer programming (MIP) is developed through this paper for the case of SDST. This new model was designed to consider fewer variables and constraints than the existing formulations. Finally, a simple problem from the literature including four jobs and four machines is resolved in order to verify the model.

Keywords

Job Shop Problem, Setup Times, Makespan, Mixed Integer Programming

Reference

[01]	Garey M. R. and Johnson D. S. (1979), Computers and intractability: a guide to the theory of NP completeness, Series of Books in the Mathematical Sciences, W. H. Freeman and company, New York.
[02]	Garey M. R., Johnson D. S. and Sethi R. (1976), The complexity of flow shop and job shop scheduling, Mathematics of Operations Research, Vol. 1 No. 2, pp. 117-129.
[03]	Allahverdi A., Gupta J. N. D. and Aldowaisan T. (1999), A review of scheduling research involving setup considerations, International Journal of Management, Vol. 27 No. 2, pp. 219-239.
[04]	Chen Z. and Pius E. J. (1989), Scheduling in manufacturing shop with sequence-dependent setups, Robotics and Computer-Integrated Manufacturing, Vol. 5 No. 1, pp. 73-81.
[05]	Moghaddas R. and Houshmand M. (2008), Job shop scheduling problem with sequence dependent setup times, Proceedings of the International Multiconference of Engineers and Computers Scientists, Vol. 2, Hong Kong, China.
[06]	Artigues C., Belmokhtar S. and Feillet D. (2004), A new exact solution algorithm for the job shop problem with sequence time setup times, International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming, Vol. 3011, Berlin, Heidelberg, pp. 37-49.
[07]	Focacci F., laborie P. and Nuijten W. (2000), Solving scheduling problems with setup times and alternatives resources, Proceedings International Conference on Artificial Intelligence Planning Systems, Vol. 5, Breckenridge, CO, USA, pp. 92-101.
[08]	Camino R. V., Ramiro V. and Miguel A. G. (2010), Local search and genetic algorithm for the job shop scheduling problem with sequence-dependent setup times, Journal of Heuristics, Vol. 16 No. 2, pp. 139-165.
[09]	Cheung W. and Zhou H. (2001), Using genetic algorithms and heuristics for job shop scheduling with sequence dependent setup times, Annals of Operations Research, Vol. 107 No. 1, pp. 65-81.
[10]	Choi I. C. and Choi D. (2002), A local search algorithm for job shop scheduling problems with alternative operations and sequence-dependent setups, Computers and Industrial Engineering, Vol. 42 No. 1, pp. 43-58.
[11]	Zhou Y., Li B. and Yang J. (2006), Study on job shop scheduling with sequence dependent setup times using biological immune algorithm, The International Journal of Advanced Manufacturing Technology, Vol. 30 No. 1, pp. 105-111.
[12]	Yang Y. (2001), A study on compound agent and its application to the enterprise management information system, Dissertation, Donghua University, Shanghai, China.
[13]	Shen L. (2014), A tabu search algorithm for the job shop problem with sequence dependent setup times, Computers and Industrial Engineering, Vol. 78, pp. 95-106.
[14]	Allahverdi A. (2015), The third comprehensive survey on scheduling problems with setup times/costs, European Journal of Operational Research, Vol. 246 No. 2, pp. 345-378.
[15]	Shen L., Dauzère-Pérès S. and Neufeld J. S. (2017), Solving the flexible job shop scheduling problem with sequence-dependent setup times, European Journal of Operational Research, Available online.
[16]	Knopp S., Dauzère-Pérès S. and Yugma C. (2017), A batch-oblivious approach for Complex Job-Shop scheduling problems, European Journal of Operational Research, Vol. 263 No. 1, pp. 50-61.
[17]	Abdelmaguid T. F., neighborhood search function for flexible job shop scheduling with separable sequence-dependent setup times, Applied Mathematics and Computation, Vol. 260, pp. 188-203.
[18]	Choi I. C. and Korkmaz O. (1997), Job shop scheduling with separable sequence-dependent setups, Annals of Operations Research, Vol. 70 No. 0, pp. 155-170.
[19]	Chinyao L., Tai-His W. and Chih-Ming H. (2005), Mathematical modeling of multi-objective job shop scheduling with dependent setups and re-entrant operations, The International Journal of Advanced Manufacturing Technology, Vol. 27 No. 1, pp. 181-189.
[20]	Manne A. S. (1960), On the job-shop scheduling problem, Operations Research, Vol. 8 No. 2, pp. 219-223.
[21]	Ku W. Y. and Christopher Beck J. (2016), Mixed Integer Programming Models for Job Shop Scheduling: A Computational Analysis, Computers and Operations Research, Vol. 73, pp. 165-173.