When serial batch scheduling involves parallel batching decisions: A branch and price scheme

Onur Öztürk

doi:10.1016/j.cor.2021.105514

2022-01-01

PRE

Onur Öztürk *

DOI：10.1016/j.cor.2021.105514

原文链接

摘要

En 中文

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.

Keyword:

Scheduling

Serial batching

Parallel batching

Branch and price