A branch-and-bound algorithm for two-machine flow-shop scheduling problems with batch delivery costs

Abstract

Manufacturers often dispatch jobs in batches to reduce delivery costs. However, this technique can have a negative effect on other scheduling-related objective functions such as minimising maximum tardiness. This paper aims to minimise the maximum tardiness and the sum of delivery costs of a two-machine flow-shop problem in a batch delivery system. It is proven in the literature that this problem is NP-complete. We present a mixed integer linear programming (MILP) model to solve the problem. As this is an MILP model, the commercial solver (the GAMS software using CPLEX solver) is not guaranteed to find the optimal solution for large-size problems at a logical CPU run time. Therefore, a branch-and-bound (B&B) algorithm is proposed for obtaining the optimum solution. Additionally, an upper bound (UB) heuristic with a quick processing time is presented. These methods are evaluated using randomly generated instances and the results indicate the efficiency of the B&B and UB heuristic algorithms.

Keywords:

• two-machine flow-shop scheduling
• maximum tardiness
• mixed integer linear programming
• branch-and-bound algorithm
• batched delivery system

Additional information

Notes on contributors

Mohammad Mahdavi Mazdeh

Mohammad Mahdavi Mazdeh is assistant professor in Department of Industrial Engineering at Iran University of Science and Technology (IUST). His major research fields include sequencing and scheduling, supply chain management, inventory management, etc. His articles have appeared in journals such as European journal of operational research, Computer & Operation research, Computer & Industrial engineering, etc.

Mohammad Rostami

Mohammad Rostami is a Ph.D. student in the Department of Industrial Engineering at Iran University of Science and Technology (IUST). His major research fields include sequencing and scheduling, supply chain management, metaheuristics algorithms, hub location, etc. His articles have appeared in journals such as Computer & Industrial engineering, KSCE journal of civil engineering, International Journal of Industrial Engineering Computations, etc.