Throughput maximization of real-time scheduling with batching
15
Citation
24
Reference
10
Related Paper
Citation Trend
Abstract:
We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and k parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + ε) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + ε, respectively. We also give approximation algorithms for two special cases when all release times are the same.Keywords:
Maximization
Batch processing
We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and k parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + ε) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + ε, respectively. We also give approximation algorithms for two special cases when all release times are the same.
Maximization
Batch processing
Cite
Citations (15)
Polynomial-time approximation scheme
Batch processing
Cite
Citations (17)
This paper addresses a problem of semi-continuous batch scheduling arising in the heating-process of blooms in steel industry,which differs from the traditional batching machine scheduling where the jobs in same batch have a starting time and a finishing time.In this model,the jobs in the same batch enter and leave the machine semi-continuously.The jobs in a batch share the longest processing time among jobs in the batch.The size of a batch is equal to the number of the jons in the batch.The processing time of a batch is equal to the total time expended from the first job in the batch entering the machine to the last one in the batch leaving the machine.Hence,the processing time of a batch deqends on the capacity of the semi-comtinuous batching machine,the longest processing time of jobs in the batch and its size.In this paper we consider the problem for minimizing makespan in chains structure.We prove the properties of the optimal solution and present a dynamic programming algorithm with a running time of O(n2),which can obtain its optimal solutions.
Batch processing
Batch production
Cite
Citations (0)
Disjoint sets
Batch processing
Cite
Citations (3)
Batch processing
Theory of computation
Batch production
Cite
Citations (1)
Batch processing
Cite
Citations (2)
In this paper we consider the problem of scheduling family jobs on a parallel-batching machine under on-line setting, Our objective is to minimize the maximum completion time of the jobs (makespan). A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the longest processing time of any job in the batch. The jobs from different families are incompatible and thus cannot be put in the same batch. We construct our schedule irrevocably as time proceeds and do not know of the existence of any job until its arrival. We deal with the special variant of the problem: the bounded model in which the capacity of the machine is limited, the jobs only have two distinct arrival times and the jobs come from m families. We provide an on-line algorithm with a worst case ratio of 2 − α over 2, where α = √5−1 over 2
Batch processing
Arrival time
Cite
Citations (3)
We consider the following scheduling with batching problem that has many applications, e.g., in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and k parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or non-explicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a non-preemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + e) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + e, respectively. We also show exact algorithms for several special cases.
Maximization
Processor scheduling
Batch processing
Cite
Citations (23)
Tardiness
Due date
Batch processing
Cite
Citations (8)
Batch processing
Decision maker
Single-machine scheduling
Cite
Citations (3)