| TR#: | MSC-2001-02 |
| Class: | MSC |
| Title: | Scheduling with Batching and Incompatible Job Families |
| Authors: | Yoav Katz |
| Supervisors: | Hadas Shachnai |
| MSC-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$. |
| Copyright | The 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