Scheduling a Bounded Parallel-Batching Machine with Incompatible Job Families and Rejection

We study a scheduling problem with incompatible job families and rejection on a parallel-batching machine,where the objective is to minimize the makespan of all accepted jobs plus the total penalty of all rejected jobs.We provide a polynomial-time algorithm for the case where all jobs have identical release dates and a pseudo-polynomial-time algorithm for the case where the number of distinct release dates is fixed.We also present a 2-approximation algorithm and a polynomial-time approximation scheme for the general problem.

Two-Agent Scheduling on a Bounded Parallel-Batching Machine with Makespan and Maximum Lateness Objectives

This paper studies the two-agent scheduling on a bounded parallel-batching machine.In the problem,there are two agents A and B each having their own job sets with the restriction that the processing times of jobs of agent B are equal.The jobs of different agents can be processed in a common batch.Moreover,each agent has its own objective function to be minimized.The objective function of agent A is the makespan of its jobs,and the objective function of agent B is the maximum lateness of its jobs.We present a polynomial-time algorithm for finding all Pareto optimal solutions of this two-agent parallel-batching scheduling problem.

Parallel-batch scheduling with deterioration and rejection on a single machine

The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the machine.Each job’s processing time is an increasing linear function of its starting time.The machine can process any number of jobs simultaneously as a batch.The processing time of a batch is equal to the largest processing time of the jobs in the batch.The objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound Q.We show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(FPTASs)for the considered problems.

Research on Unbounded Parallel-Batch Scheduling with Jobs Having Set-Up Times

We study the scheduling on an unbounded parallel-batch machine with jobs having set-up times to minimize a regular objective function which is either of the sumform or of the max-form.As we know,in the existing literature,the research about parallel-batch scheduling does not consider the set-up times of jobs.However,the set-up times of jobs are widely presented in practical applications.Each job considered in this paper has a set-up time.The set-up time of each batch is equal to the maximum set-up time of all jobs contained in the batch,and the processing time of each batch is equal to the longest processing time of the jobs contained in the batch.Depending on the different definitions of the completion time of a job,we consider two types of jobs:batch jobs and drop-line jobs.For batch jobs,the completion time of a job is given by the completion time of the batch containing this job.For drop-line jobs,the completion time of a job is given by the starting time of the batch containing this job plus the processing time of this job.In this paper,we give pseudo-polynomial time algorithms for the above scheduling problems in which the jobs have agreeable processing times and set-up times.In addition,when the objective functions are the total weighted completion time,the maximum lateness,and the maximum cost,we present a polynomial time algorithm,respectively.

Online Parallel-Batch Machines Scheduling with a Single Server

We consider parallel-batch machines scheduling problem with a single server to minimize the maximum completion time.Jobs arrive over time.Every batch has to be loaded by the sever before being processed on machines.The loading(setup)operation of a batch occurs only when some machine is idle,and the server can perform only one setup operation every time.For some special case,we provide a best possible online algorithm with competitive ratio■.For general case,we give another online algorithm with competitive ratio 3.

A Note on DP Algorithm for Batching Scheduling to Minimize Maximum Lateness

In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n^2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.

Online Over Time Scheduling on Parallel-Batch Machines:A Survey

Online scheduling is a rapidly developed branch in scheduling theory.In this paper,we present an extensive survey for online over time scheduling on parallel-batch machines.Some open problems are proposed for further research.

Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan

We study an online(over time)scheduling problem on two uniform unbounded parallel-batch machines with processing speed 1 and v(0<≤1),respectively,to minimize the makespan.We first show that no online algorithm can have a competitive ratio less than 1+αL,whereαL=(√5−1)/2≈0.618 if 0≤1/2,andαL=α2(v)is the positive root ofα^(3)+3α^(2)+(3−1/v)α−1/v=0 if1/2≤1.This lower bound is still valid when all jobs have the same processing times.Then,we provide an online algorithm with a competitive ratio at most min{(√5+1)/2,√2/v}.When the jobs have the same processing times,we present the best possible online algorithm with a competitive ratio 1+αL.