Heuristic control of multiple batch processors with incompatible job families and future job arrivals

• Main Authors: Tajan, John Benedict C., Sivakumar, Appa Iyer., Gershwin, Stanley B.
• Other Authors: School of Mechanical and Aerospace Engineering
• Format: Article
• Language: English
• Published: 2013
• Subjects: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
• Online Access: https://hdl.handle.net/10356/104295; http://hdl.handle.net/10220/16994
• Institution: Nanyang Technological University

We analyse the problem of minimising the mean cycle time of a batch processing stage containing K > 1 batch processors in parallel with incompatible job families and future job arrivals. We provide an integer linear programming formulation and a dynamic program formulation for small problem instances. For larger problem instances, we propose an online heuristic policy MPC_REPEAT. At each instance a decision has to be made, MPC_REPEAT decomposes the problem of simultaneously assigning multiple batches to multiple processors into sequentially assigning multiple batches to multiple processors. When job families are uncorrelated, we show via simulation experiments that MPC_REPEAT has significantly lower mean cycle time than a previously proposed look-ahead method except when: (MPC_REPEAT ignores some job families AND the traffic intensity is high.) Our experiments also reveal that increasing the job family correlation of consecutive job arrivals results, with a few exceptions, in a mean cycle-time reduction, for both policies evaluated. This reduction in cycle time generally increases with: increasing number of job families, decreasing number of processors, and increasing time between job arrivals. Our findings imply that controlling the upstream processors, such that job families of consecutive job arrivals are correlated, can reduce the cycle time at the batch processing stage. Furthermore, the expected mean cycle time reduction due to this strategy can be substantially larger than that expected from switching to a more complex batch processing stage policy, under less stringent conditions.