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 PDF 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.