Paper Info
Title
When Serial Batch Scheduling Involves Parallel Batching Decisions: A Branch And Price 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, n-ary sumation Sigma C-j) and total weighted tardiness (n-ary sumation Sigma 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 n-ary sumation Sigma w(j)T(j) objective and prove its optimality for n-ary sumation Sigma C-j objective. Numerical test results show that the algorithm can handle large instances in reasonable computational times.
Year
DOI
Venue
2022
10.1016/j.cor.2021.105514
COMPUTERS & OPERATIONS RESEARCH
Keywords
DocType
Volume
Scheduling, Serial batching, Parallel batching, Branch and price
Journal
137
ISSN
Citations 
PageRank 
0305-0548
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Onur Ozturk100.68