TY - JOUR

T1 - Batch scheduling of identical jobs with controllable processing times

AU - Mor, Baruch

AU - Mosheiov, Gur

N1 - Funding Information:
This paper was supported in part by The Charles Rosen Chair of Management and the Recanati Fund of The School of Business Administration, The Hebrew University, Jerusalem, Israel.

PY - 2014

Y1 - 2014

N2 - In scheduling models with controllable processing times, the job processing times can be controlled (i.e. compressed) by allocating additional resources. In batch scheduling a large number of jobs may be grouped and processed as separate batches, where a batch processing time is identical to the total processing times of the jobs contained in the batch, and a setup time is incurred when starting a new batch. A model combining these two very popular and practical phenomena is studied. We focus on identical jobs and linear compression cost function. Two versions of the problem are considered: in the first we minimize the sum of the total flowtime and the compression cost, and in the second we minimize the total flowtime subject to an upper bound on the maximum compression. We study both problems on a single machine and on parallel identical machines. In all cases we introduce closed form solutions for the relaxed version (allowing non-integer batch sizes). Then, a simple rounding procedure is introduced, tested numerically, and shown to generate extremely close-to-optimal integer solutions. For a given number of machines, the total computational effort required by our proposed solution procedure is O(n), where n is the number of jobs.

AB - In scheduling models with controllable processing times, the job processing times can be controlled (i.e. compressed) by allocating additional resources. In batch scheduling a large number of jobs may be grouped and processed as separate batches, where a batch processing time is identical to the total processing times of the jobs contained in the batch, and a setup time is incurred when starting a new batch. A model combining these two very popular and practical phenomena is studied. We focus on identical jobs and linear compression cost function. Two versions of the problem are considered: in the first we minimize the sum of the total flowtime and the compression cost, and in the second we minimize the total flowtime subject to an upper bound on the maximum compression. We study both problems on a single machine and on parallel identical machines. In all cases we introduce closed form solutions for the relaxed version (allowing non-integer batch sizes). Then, a simple rounding procedure is introduced, tested numerically, and shown to generate extremely close-to-optimal integer solutions. For a given number of machines, the total computational effort required by our proposed solution procedure is O(n), where n is the number of jobs.

KW - Batch scheduling

KW - Controllable processing times

KW - Flowtime

KW - Parallel identical machines

KW - Single machine

UR - http://www.scopus.com/inward/record.url?scp=84883461499&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2013.08.007

DO - 10.1016/j.cor.2013.08.007

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84883461499

SN - 0305-0548

VL - 41

SP - 115

EP - 124

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 1

ER -