Scheduling parallel-machine batch operations to maximize on-time delivery performance

Document Type

Article

Publication Date

10-1-2016

Abstract

In this paper we study the problem of minimizing total weighted tardiness, a proxy for maximizing on-time delivery performance, on parallel nonidentical batch processing machines. We first formulate the (primal) problem as a nonlinear integer programming model. We then show that the primal problem can be solved exactly by solving a corresponding dual problem with a nonlinear relaxation. Since both the primal and the dual problems are NP-hard, we use genetic algorithms, based on random keys and multiple choice encodings, to heuristically solve them. We find that the genetic algorithms consistently outperform a standard mathematical programming package in terms of solution quality and computation time. We also compare the smaller problem instances to a breadth-first tree search algorithm that gives evidence of the quality of the solutions.

DOI

10.1007/s10951-015-0449-6

Publication Title

Journal of Scheduling

Volume Number

19

Issue Number

5

First Page

583

Last Page

600

ISSN

10946136

This document is currently not available here.

Share

COinS