The Single Machine Parallel-batching Scheduling Problem With Family-jobs

Scheduling is to assign jobs on machines under some constraints such that one-or multi-critcria attain to the optimum. Parallel batch scheduling is a flourishing scheduling model. Scheduling with family jobs is a new concept in the parallel batch scheduling.In this paper, we consider the single machine parallel batching scheduling problem with family jobs under the restriction that the processing times of all jobs belonging to the same family are equal. Our study include: (1) The single machine parallel batch scheduling problem of minimizing total weighted completion time with family jobs on a single batch processing machine with the restriction that the processing times of the jobs in the same family are equal. (2) The single machine parallel batch scheduling problem to minimize the number of tardy jobs with family jobs and the restriction that the processing times of the jobs in the same family are equal.Parallel batch scheduling means that a machine can process several jobs simultaneously as a batch, and all jobs in a batch start and complete at the same time, respectively. The processing time of a batch is equal to the longest processing time of all the jobs in the batch. Once the processing of batch is initiated, it cannot be interrupted, nor can other jobs be added into the batch.The problems that we studied in this paper can be formulated as the following model:We are given a set of n jobs {J₁, J₂,…,J_n}, which can be partitioned into m incompatiblefamilies. The processing times of all jobs belong to the same family are equal and jobs of different families cannot be processed together. The jobs are processed in batches, where a batch is a subset of jobs and we require that the batches (subsets) form a partition of the set of all jobs. We call this model the parallel-batching scheduling problem and denote it bywhere f is one ofΣw_jC_j orΣU_j.The main conclusion of this paper as follows:(1) The problem of minimizing total weighted completion time with family jobs on a single batch processing machine under the restriction that the processing times of jobs in the same family are equal.Based on the analysis of the quality of the optimal solution for the total weighted completion time of parallel-batching, we propose the optimal nature batches, and the process times are equal in the same family, the optimal sequencing rules of bounded model and unbounded model are given, respectively. When there are a constant number of job release dates, we provide two heuristic algorithms and analyse its complexity for the bounded model and the unbounded model.(2) Minimizing number of tardy jobs on a batch processing machine with family jobs.For these cases that either r and d are agreeable or p and d are agreeable, some qualities of the optimal solution are given in this paper. We provide the dynamicprogramming algorithm with a time bound O(?). When m is a fixed constant, thisis polynomial-time algorithm. We also discuss a special case of the problem where the jobs belonging to the same family have a common due date, and give a pseudo-polynomial-time algorithm.