Mixed Integer Linear Programming Based Heuristic for Job Shop Scheduling Problem

Main Article Content

Jakrawarn Kunadilok
Patcharin Srisongsakun
Sanya Yimsiri
Ruephuwan Chantrasa


This research proposed a scheduling method for an automotive part manufacturing process with job shop production environment. A mixed integer linear programming based heuristic (MILP_H) was designed for dividing a group of job orders to several subgroups in case that number of jobs to be scheduled is large. Then the proposed mixed integer linear programming (MILP) models are used for generating a schedule for each subgroup. If all jobs in the subgroup have completed before their due date ,the MILP with minimizing makespan will be chosen for scheduling. Otherwise, the MILP with minimizing total weighted makespan and maximum lateness will be used to lessen the extra time for producing the tardy jobs to finish their production within due date. The subgroup schedules then are combined as a production schedule for practice. The 15-problem set consists of real and simulation scheduling problems was used for perfomance test. The results revealed that the MILP_H can create production schedules with 4.22% reduction in average makespan and 22.62% decrease in the average of the maximum lateness.

Article Details

How to Cite
Kunadilok, J., Srisongsakun , P. ., Yimsiri , S., & Chantrasa , R. . (2021). Mixed Integer Linear Programming Based Heuristic for Job Shop Scheduling Problem. Thai Industrial Engineering Network Journal, 7(2), 29–40. Retrieved from https://ph02.tci-thaijo.org/index.php/ienj/article/view/242053
Research and Review Article


[1] Pinedo, ML. Scheduling: Theory, Algorithms, and Systems. New Jersey: Prentice-Hall; 2002.
[2] Wanlapa Kowmanee. Job-Shop scheduling by using heuristic method for FIFO management system development [Master’s thesis in Manufacturing Engineering]. Kuala Lumpur; University of Malaya; 2014.
[3] ปารเมศ ชุติมา. เทคนิคการจัดตารางการดำเนินงาน. พิมพ์ครั้งที่ 2. กรุงเทพฯ: สำนักพิมพ์แห่งจุฬาลงกรณ์มหาวิทยาลัย; 2555.
[4] Jain AS, Meeran S. Deterministic Job-shop Scheduling: Past, Present and Future. European Journal of Operational Research. 1999; 113: 390-434.
[5] Garey MR, Johnson, DS. Computers and Intractability: a Guide to the Theory of NP-completeness. New York: Willey; 1979.
[6] Blazewicz J, Dror M, Weglarz J. Mathematical Programming Formulations for Machine Scheduling: a Survey. European Journal of Operational Research. 1991; 51: 283-300.
[7] Pan JCH. A Study of Integer Programming Formulations for Scheduling Problems. International Journal of Systems Science. 1997; 28: 33-41.
[8] Pan JCH, Chen JS. Mixed Binary Integer Programming Formulations for the Reentrant Job Shop Scheduling Problem. Computers & Operations Research. 2005; 32: 1197-1212.
[9] Kunadilok J, Kurz ME. Mixed integer programming for scheduling flexible reentrant job shop problems. In Proceedings of the Annual Industrial Engineering Research Conference; 2005 May 15-18; Atlanta, Gorgia, USA. 2005. CD version.
[10] Mason AJ. OpenSolver – An Open Source Add-in to Solve Linear and Integer Progammes in Excel. In Proceedings of Operations Research Conference; 2011 Aug 30 - Sep 2; Zurich, Switzerland. 2012. p. 401-406.
[11] Gurobi Optimization Inc. Gurobi Optimizer Reference Manual. [cited 2016 May 10] Retrieved from http://www.gurobi.com