Technical Report MSC-2001-02

TR#:MSC-2001-02
Class:MSC
Title: Scheduling with Batching and Incompatible Job Families
Authors: Yoav Katz
Supervisors: Hadas Shachnai
PDFMSC-2001-02.pdf
Abstract: We consider the problem of batch scheduling of jobs from incompatible families, which arises in production systems, in multimedia-on-demand services, and in many real-life scenarios. Suppose that $n$ jobs need to be scheduled on $m$ batching machines, that is, machines that can run several jobs simultaneously. Each job is given by its family, release date, due date, and non-negative weight; jobs from the same family have the same processing time. The machines can process the jobs in batches of size at most $b$, with the restriction that jobs from different families cannot be batched together. Our objective is to find a schedule of the jobs, which maximizes the overall weight of on-time jobs (i.e., jobs that are scheduled before their due dates). We call this problem the {\em f-batch} problem. Our problem is a generalization of classical real-time scheduling; thus, it is strongly NP-hard.

We first give a detailed characterization of optimal schedules, which enables to develop efficient polynomial time algorithms for our problem. Specifically, we formulate a set of structural properties satisfied by optimal schedules. We then use these properties to obtain optimal solutions for several important classes of instances.

A main contribution of this work is a technique for transforming the f-batch problem to a variant of classical real-time scheduling. This transformation is used for deriving the first combinatorial approximation algorithm for the f-batch problem. Our transformation yields a simple $(2+ \epsilon)$-approximation algorithm for general instances with unbounded batch size, based on the Local Ratio technique of Bar-Yehuda and Even ({\em Annals of Discrete Mathematics}, vol. 25, 1985, pp. 27-46). The algorithm can be applied with the same performance ratio to a system of $m$ identical machines, for any $m>1$.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2001/MSC/MSC-2001-02), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2001
To the main CS technical reports page

Computer science department, Technion