Back to Top

Paper Title

Parallel-batching scheduling of deteriorating jobs with non-identical sizes and rejection on a single machine

Article Type

Research Article

Research Impact Tools

Issue

Volume : 14 | Page No : 857–871

Published On

January, 2019

Downloads

Abstract

This paper studies the bounded parallel-batching scheduling problem considering job rejection, deteriorating jobs, setup time, and non-identical job sizes. Each job will be either rejected with a certain penalty cost, or accepted and further processed in batches on a single machine. There is a setup time before processing each batch, and the objective is to minimize the sum of the makespan and the total penalty. Several useful preliminaries for arranging accepted job with identical size are proposed. Based on these preliminaries, we first investigate a special case where all the jobs are considered to have the identical size, and develop a dynamic programming algorithm to solve it. The preliminaries help to reduce the complexity of the dynamic programming algorithm from O(n!n2∑i=1nwj) to O(n2∑i=1nwj). For the general problem with non-identical job sizes, we propose a hybrid algorithm combining heuristic with dynamic programming algorithm (H-DP) to obtain satisfactory solutions within reasonable time. Finally, the effectiveness and efficiency of the H-DP algorithm are illustrated by a series of computational experiments.

View more >>