# A Novel Fast Parallel Batch Scheduling Algorithm for Solving the Independent Job Problem
## 1 Introduction  
How to reduce the production cycle and improve the utilization rate of resources is an important problem under the constraints of workshop production, such as delivery time, technical requirements and resource status, etc. Most enterprises adopt workshop scheduling technology to solve this problem. An effective scheduling optimization method can take advantage of many production resources in the workshop. The research and application of a workshop scheduling optimization method has become one of the basic contents of advanced manufacturing technology [1; 2; 3]. Batch processing machines (BPMs) are widely applied in many enterprises, for example, steel casting, chemical and mineral processing, and so on [4; 5; 6]. BPMs scheduling problem is a hot topic in workshop scheduling problem. In the traditional scheduling problem, each machine can only process, at most, one job at a time [7]. However, BPMs can process a number of jobs simultaneously as a batchand all jobs in a batch have the same processing time [8]. The processing time of one batch is equal to the maximum processing time of all the jobs processed by the batch [9]. In this paper, we analyze the parallel batch processing machine scheduling problem where the jobs have arbitrary size and the machines have different capacities. We give a set of \(n\) jobs \(\mathcal{J}=\{J_{1},J_{2},\ldots,J_{n}\}\) and a set of \(m\) parallel batch machines \(\mathcal{M}=\{M_{1},M_{2},\ldots,M_{m}\}\), and we let all the jobs be released simultaneously (release time of job is \(0\)). Let \(p_{j}\) and \(s_{j}\) denote the processing time and the size of job \(J_{j}\in\mathcal{J}\)\((j=1,2,\ldots,n)\), respectively, where \(p_{j}\geq 0\) and \(s_{j}>0\). Machine \(M_{i}\)\((i=1,2,\ldots,m)\) has a finite capacity \(K_{i}\). Without loss of generality, we assume \(K_{1}\leq K_{2}\leq\cdots\leq K_{m}\) and \(s_{j}\leq K_{m}\) for each job \(J_{j}\) in order to ensure job \(J_{j}\) can be processed by at least one machine. However, there might be \(s_{j}>K_{i}\) for some \(J_{j}\) and \(M_{i}\). Machine \(M_{i}\)\((i=1,2,\ldots,m)\) can handle multiple jobs at the same time, but the total size of these jobs cannot exceed \(K_{i}\). The longest processing time of all jobs in a batch determines the processing time of a batch. The purpose of this problem is to allot each job to a batch and to schedule the batch on the machine to minimize the maximum completion time of the schedule, \(C_{\max}=\max_{j}C_{j}\), where \(C_{j}\) represents the completion time of job \(j\) in the schedule [10; 11]. Using the notations proposed in [12; 13], this problem can be denoted as \(P\big{|}s_{j},p-batch,K_{i}\big{|}C_{\max}\). The notations used in this paper are summarized in Table 1.  
Before we move on, let us introduce some useful notations and terminologies. Let \(\mathcal{J}_{i}=\big{\{}J_{j}\in\mathcal{J}\big{|}K_{i-1}<s_{j}\leq K_{i}\big{\}}\), and \(i=1,2,\ldots,m,j=1,2,\ldots,n\); when \(i=1\), \(K_{0}\) was used, but it was meaningless, so we set \(K_{0}=0\). It is possible that \(\mathcal{J}_{i}=\phi\) for some \(i\). We have \(\mathcal{J}=\cup_{i=1}^{m}\mathcal{J}_{i}\). Let \(a_{j}=i\) denote the index of a machine with the minimum capacity that can process the job \(J_{j}\in\mathcal{J}_{j}\), and then \(J_{j}\) can be assigned to each machine in \(\mathcal{M}_{j}=\big{\{}M_{a_{j}},M_{a_{j}+1},\ldots,M_{m}\big{\}}\) where \(1\leq a_{j}\leq m\). \(M_{a_{j}},M_{a_{j}+1},\ldots,M_{m}\) are called the golden machines for job \(J_{j}\), \(\mathcal{M}_{j}\) is the golden machines set, \(J_{j}\) is called the golden job for \(M\in\mathcal{M}_{j}\), and all of the jobs that can be processed by \(M_{i}\) are called the golden jobs set for \(M_{i}\). In a scheduling process, the running time of the machine is equal to the total processing time of batches scheduled on this machine. The structure of the paper is as follows. Section 2 reviews the previous research in related areas. Section 3 gives the definition of the research problem.