When serial batch scheduling involves parallel batching decisions: A branch and price scheme. (January 2022)

• Record Type: Journal Article
• Authors: Ozturk, Onur
• Is Part Of: Computers & operations research. Volume 137(2022)
• Publication Date: 2022-01
• Subjects: Scheduling -- Serial batching -- Parallel batching -- Branch and price; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105514
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: Serial batching and parallel batching nested within each other. Flow time and total weighted tardiness minimization. Time indexed integer formulation solved by column generation. Pseudo-polynomial time algorithm for the sub-problem. Branch and price algorithm employing a novel branching scheme. Abstract: This paper studies a scheduling problem in which serial and parallel batching decisions must be simultaneously taken. There is a single machine with a fixed capacity that can process multiple jobs at the same time (i.e., parallel batching). Throughout the planning horizon, jobs are released at different instants and they belong to different families. Each job requires one unit of the machine capacity and only jobs of the same family can be processed at the same time. Once a group of jobs is decided to be processed, a preparation time occurs and all jobs are considered completed when the last job of the group finishes its processing (i.e., serial batching). We aim to minimize total flow time (i.e., sum of job completion times, ∑ C j ) and total weighted tardiness ( ∑ w j T j ) objectives. First, we formulate this problem as an integer linear programming model. Then, we develop a column generation algorithm to solve the linear relaxation which is integrated in a branch and bound tree in search for the integer solution. We use a highly efficient heuristic branching technique for ∑ w j T j objective and prove its optimality for ∑ C j objective. Numerical test results show that the algorithm can handle large instances in reasonable computational times.