Mixed integer lineal programming model to schedule flexible job-shop systems in make to order environments
DOI:
https://doi.org/10.17981/ingecuc.13.2.2017.03Keywords:
Production schedule, Flexible job shop, Mixed integer lineal programming, tardy jobsAbstract
Introduction: Job Shop (JS) production systems are characterized by different route process of the Jobs to be processed. A generalization of this type of systems is the Flexible Job Shop (FJS), in which there is more than one machine per station to perform some of the operations.
Objective: The objective of this project was to propose a mixed integer linear programming model to program FJS systems in order to minimize the number of tardy jobs.
Methodology: The model was developed using an approach based on sequence-position variables. This approach uses binary variables to decide whether a given operation is assigned to a position in the processing sequence of the assigned machine. To validate the performance of the model data from a small company with an FJS type production system, that develops its operations in an environment to order (MTO), was used. For this reason, the most important performance indicators for the company are those associated with the service level.
Results: The results show a reasonable performance in terms of the objective pursued. The optimal production schedule was found in less than 3600 seconds in instances of less than 14 production orders. In larger instances, it obtained feasible solutions within the defined time limit.
Conclusions: The model allows defining production schedules in systems in which the fulfillment of due dates is of vital importance. The results have allowed the company to improve its performance and reduce the costs associated with non-compliance of customer’s due dates. Future research can be developed to find more efficient solution methods in terms of computational times to obtain solutions of larger instances.
Downloads
References
[2] M. Mastrolilli and L. M. Gambardella, “Effective Neighborhood Functions for the Flexible Job Shop Problem!,” J. Sched., vol. 3, no. 1, pp. 3–20, 1999. Disponible: http://dx.doi.org/10.1002/(SICI)1099-1425(200001/02)3:1<3::AID-JOS32>3.0.CO;2-Y
[3] C. R. Scrich, V. A. Armentano, and M. Laguna, “Tardiness Minimization in a Flexible Job Shop: A Tabu Search Approach,” J. Intell. Manuf., vol. 15, no. 1, pp. 103–115, 2004. Disponible: http://dx.doi.org/10.1023/B:JIMS.0000010078.30713.e9
[4] Z. Wu and M. X. Weng, “Multiagent scheduling method with earliness and tardiness objectives in flexible job shops,” IEEE Trans. Syst. Man, Cybern. Part B, vol. 35, no. 2, pp. 293–301, 2005. Disponible: https://doi.org/10.1109/TSMCB.2004.842412
[5] N. Zribi, A. El Kamel, and P. Borne, “Total tardiness in a flexible job-shop,” in IMACS Multiconference on “Computational Engineering in Systems Applications”, CESA, 2006, pp. 1543–1549. Disponible: https://doi.org/10.1109/CESA.2006.4281882
[6] J. C. Tay and N. B. Ho, “Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems,” Comput. Ind. Eng., vol. 54, no. 3, pp. 453–473, 2008. Disponible: https://doi.org/10.1016/j.cie.2007.08.008
[7] A. Baykasoglu and L. Özbakir, “Analyzing the effect of dispatching rules on the scheduling performance through grammar based flexible scheduling system,” Int. J. Prod. Econ., vol. 124, no. 2, pp. 369–381, 2010. Disponible: https://doi.org/10.1016/j.ijpe.2009.11.032
[8] K. Thörnblad, “On the optimization of schedules of a multitask production cell,” 2011. Disponible: http://publications.lib.chalmers.se/records/fulltext/144904.pdf
[9] J. C. Chen, C.-C. Wu, C.-W. Chen, and K.-H. Chen, “Flexible job shop scheduling with parallel machines using Genetic Algorithm and Grouping Genetic Algorithm,” Expert Syst. Appl., vol. 39, no. 11, pp. 10016–10021, 2012. Disponible: https://doi.org/10.1016/j.eswa.2012.01.211
[10] L. Lin, M. Gen, Y. Liang, and K. Ohno, “A hybrid EA for reactive flexible job-shop scheduling,” in Procedia Computer Science, 2012, vol. 12, pp. 110–115. Disponible: https://doi.org/10.1016/j.procs.2012.09.039
[11] M. C. Gomes, A. P. Barbosa-Póvoa, and A. Q. Novais, “Reactive scheduling in a make-to-order flexible job shop with re-entrant process and assembly: a mathematical programming approach,” Int. J. Prod. Res., vol. 51, no. 17, pp. 5120–5141, 2013. Disponible: http://dx.doi.org/10.1080/00207543.2013.793428
[12] R.-H. Huang, C.-L. Yang, and W.-C. Cheng, “Flexible job shop scheduling with due window—a two-pheromone ant colony approach,” Int. J. Prod. Econ., vol. 141, no. 2, pp. 685–697, 2013. Disponible: https://doi.org/10.1016/j.ijpe.2012.10.011
[13] M. Mousakhani, “Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness,” Int. J. Prod. Res., vol. 51, no. 12, pp. 3476–3487, 2013. Disponible: http://dx.doi.org/10.1080/00207543.2012.746480
[14] A. Sadrzadeh, “Development of Both the AIS and PSO for Solving the Flexible Job Shop Scheduling Problem,” Arab. J. Sci. Eng., vol. 38, no. 12, pp. 3593–3604, Dec. 2013. Disponible: http://doi.org/10.1007/s13369-013-0625-y
[15] K. Thörnblad, A.-B. Strömberg, M. Patriksson, and T. Almgren, “An efficient algorithm for solving the flexible job shop scheduling problem,” in 25th NOFOMA conference proceedings, June 3-5 2013, Göteborg, Sweden, 2013. Disponible: http://publications.lib.chalmers.se/records/fulltext/181796/local_181796.pdf
[16] G. Calleja and R. Pastor, “A dispatching algorithm for flexible job-shop scheduling with transfer batches: an industrial application,” Prod. Plan. Control, vol. 25, no. 2, pp. 93–109, 2014. Disponible: http://dx.doi.org/10.1080/09537287.2013.782846
[17] Y. Liu, H. Dong, N. Lohse, S. Petrovic, and N. Gindy, “An investigation into minimising total energy consumption and total weighted tardiness in job shops,” J. Clean. Prod., vol. 65, pp. 87–96, 2014. Disponible: https://doi.org/10.1016/j.jclepro.2013.07.060
[18] H. Na and J. Park, “Multi-level job scheduling in a flexible job shop environment,” Int. J. Prod. Res., vol. 52, no. 13, pp. 3877–3887, 2014. Disponible: http://dx.doi.org/10.1080/00207543.2013.848487
[19] K. Z. Gao, P. N. Suganthan, Q. K. Pan, T. J. Chua, T. X. Cai, and C. S. Chong, “Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives,” J. Intell. Manuf., vol. 27, no. 2, pp. 363–374, Apr. 2016. Disponible: http://doi.org/10.1007/s10845-014-0869-8
[20] O. Faura Gatius, “Flexible Job-Shop Problem minimizando los costes en función de la fecha de entrega y el instante de realización,” Universitat Politécnica de Catalunya, 2016. Disponible: http://hdl.handle.net/2117/98534
[21] A. Türkyılmaz and S. Bulkan, “A hybrid algorithm for total tardiness minimisation in flexible job shop: genetic algorithm with parallel VNS execution,” Int. J. Prod. Res., vol. 53, no. 6, pp. 1832–1848, Mar. 2015. Disponible: http://dx.doi.org/10.1080/00207543.2014.962113
[22] Y. Demir and S. Kürşat Işleyen, “Evaluation of mathematical models for flexible job-shop scheduling problems,” Appl. Math. Model., vol. 37, no. 3, pp. 977–988, 2013. Disponible: https://doi.org/10.1016/j.apm.2012.03.020
Downloads
Additional Files
Published
How to Cite
Issue
Section
License
Published papers are the exclusive responsibility of their authors and do not necessary reflect the opinions of the editorial committee.
INGE CUC Journal respects the moral rights of its authors, whom must cede the editorial committee the patrimonial rights of the published material. In turn, the authors inform that the current work is unpublished and has not been previously published.
All articles are licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
English
Español (España)
