Customer order scheduling with lot streaming to minimize the total order completion time in a two-machine flow shop

In this study, we consider a customer order scheduling problem in which each customer can request a variety of products (also called jobs) in an order. All products are processed on a two-machine flow shop in which each product has one operation on each machine, and all products are first processed by machine 1 and then by machine 2. Each customer order is delivered to the customer when the processing of all products in the customer order is completed. Thus, the completion time of the job sublot processed as the last product in a customer order defines the completion time of the customer order. Our goal is to find a sequence of the job lots as well as the sequences of the sublots in each job so that the total completion time, which is the sum of the completion times of the customer orders, is minimized. We develop a mixed integer linear programming model capable of solving small-sized problem instances optimally, and propose a tabu-search based heuristic algorithm that obtains optimal and near-optimal solutions for medium and large-sized problem instances. The results of our computational experiments performed to evaluate the performance of our solution approaches in terms of both quality and time show that the proposed heuristic algorithm finds optimal or near-optimal solutions in very short time.