Mathematical Formulation to Minimize Makespan in a Job Shop with a Batch Processing Machine
Miguel Rojas-Santiago
| ||
Mathematical Formulation to Minimize Makespan in a Job Shop with a Batch Processing Machine | ||
| Published in: | Engineering for a Smarter Planet: Innovation, ITC, and Computational Tools for Sustainable Development: Proceedings of the 9th Latin American and Caribbean Conference for Engineering and Technology | |
| Date of Conference: | August 3-5, 2011 | |
| Location of Conference: | Medellin, Colombia | |
| Authors: | Purushothaman Damodaran Miguel Rojas-Santiago | |
| Refereed Paper: | #166 | |
Abstract | ||
| We consider a scheduling problem commonly observed in the metal working industry. We analyze a job shop which is equipped with one batch processing machine (BPM), and several unit-capacity machines. Given a set of jobs, their process routes, processing requirements, and size, the objective is to schedule the jobs such that the makespan is minimized. The BPM can process a batch of jobs as long as the total batch size does not exceed the machine capacity. The batch processing time is equal to the longest processing job in the batch. The problem under study can be represented as Jm|batch|Cmax, using the three field notation. If no batches were to be formed, the scheduling problem under study reduces to Jm||Cmax, which is known to be NP-hard. A network representation of the problem using disjunctive and conjunctive arcs, and a Mixed-Integer Linear Programming (MILP) are proposed to solve the problem. An experimental study was conducted to evaluate the proposed mathematical formulation. | ||