Makespan minimization on single batch-processing machine via ant colony optimization

Abstract

This paper investigates the problem of minimizing makespan on a single batch-processing machine, and the machine can process multiple jobs simultaneously. Each job is characterized by release time, processing time, and job size. We established a mixed integer programming model and proposed a valid lower bound for this problem. By introducing a definition of waste and idle space ($\mathcal{WIS}$), this problem is proven to be equivalent to minimizing the $\mathcal{WIS}$ for the schedule. Since the problem is NP-hard, we proposed a heuristic and an ant colony optimization (ACO) algorithm based on the theorems presented. A candidate list strategy and a new method to construct heuristic information were introduced for the ACO approach to achieve a satisfactory solution in a reasonable computational time. Through extensive computational experiments, appropriate ACO parameter values were chosen and the effectiveness of the proposed algorithms was evaluated by solution quality and run time. The results showed that the ACO algorithm combined with the candidate list was more robust and consistently outperformed genetic algorithm (GA), CPLEX, and the other two heuristics, especially for large job instances.

Introduction

Batching scheduling in a manufacturing system is a very common policy in most industries. The main reasons for batching are avoidance of setups and/or facilitation of material handling. Batching occurs in two versions: serial batching and parallel batching. On a serial batching machine, the length of a batch equals the sum of the processing times of its jobs. On a parallel batching machine, several jobs can be processed as a batch simultaneously on a machine at one time and the length of a batch is the largest processing time of its jobs. This paper focus on in the context of parallel batching scheduling. In the literature, the parallel batching scheduling is also known as scheduling of batch-processing machine (BPM) [1], [2], [3].

In a BPM, jobs are grouped to constitute batches. All jobs contained in a batch are processed simultaneously and then released together from the machine together. The BPM is able to process a group of jobs as long as the sum of job sizes in the batch is less than or equal to the capacity of the machine. The processing time of a batch is equal to the longest processing time of all the jobs in that batch. Once a batch is being processed, the batch-processing machine cannot be interrupted; no jobs can be removed from the machine until the process is completed.

The BPM problem is motivated by the burn-in operation found in the final testing phase in semiconductor manufacturing [4], [5], [6]. The purpose of the final testing phase is to test the integrated circuits for defects. A burn-in oven is used in this phase, subjecting the circuits to thermal stress for an extended period of time. In this way, latent defects may be discovered that would otherwise only be found in the operating environment.

This problem is important because the scheduling of batching operations has a significant economic impact. The processing times of batching operations in burn-in operation are extremely long when compared to other operations. These operations constitute a bottleneck in the final testing phase, consequently efficient scheduling to maximize throughput is of great concern in productivity and on-time delivery management. Moreover, the BPM problem is encountered in many discrete parts manufacturing industries such as shoe manufacturing industry [7], casting industry [8], furniture manufacturing industry [9], metal industry [10], and aircraft industry [11].

In recent years, a body of research has addressed the scheduling problem on a single batch-processing machine. Ikura and Gimple [12] were probably the first to study the BPM problem. They proposed an $O(n^2)$ algorithm for the single batch machine problem with identical job processing times, unit job sizes, dynamic job arrivals, and an objective of minimizing makespan. Lee et al. [13] first presented a detailed description for burn-in operation and then studied the problem in which the processing time of jobs are identical and the relationship of release time $(r_i)$ and due date $(d_i)$ of a job $J_i$ is agreeable, i.e., $r_i\le r_j$ implies $d_i\le d_j$. They considered minimizing maximum lateness $(L_{\mathit{max}})$ and the number of tardy jobs $(\sum U_i)$ using dynamic programming algorithms. Uzsoy and Yang [14] considered the problem of minimizing total weighted completion time $(\sum {\omega }_i{C}_i)$ and provided several heuristics and a branch-and-bound algorithm. Jolai [15] showed that the problem of minimizing $\sum U_i$ is NP-hard. He developed a dynamic programming algorithm with polynomial time complexity for the fixed number of job families and limited batch machine capacity.

Considering jobs with non-identical sizes, Uzsoy [16] presented complexity results for minimizing makespan $(C_{\mathit{max}})$ and total completion time $(\sum C_i)$ criteria. He also provided several heuristics and a branch-and-bound algorithm. To schedule a batch-processing machine for minimizing $C_{\mathit{max}}$ with different job sizes, Melouk et al. [17] and Damodaran et al. [18] proposed two different algorithms: a simulated annealing approach and a genetic algorithm, respectively. Kashan et al. [19] proposed two different genetic algorithms based on different encoding schemes to minimize $C_{\mathit{max}}$ with non-identical job sizes. Kashan and Karimi [20] developed an ant colony framework in two versions, depending on the type of embedded heuristic information, to minimize $\sum {\omega }_i{C}_i$ on a single batch-processing machine with incompatible job families and arbitrary job sizes.

Considering jobs with arbitrary release dates, Lee and Uzsoy [21] first presented polynomial and pseudopolynomial-time algorithms for several special cases and developed various heuristics for minimizing makespan on a single batch-processing machine in the presence of dynamic job arrivals. Sung and Choung [22] proposed some heuristics to minimize $C_{\mathit{max}}$ on a single burn-in oven in semiconductor manufacturing with different job release times. Wang and Uzsoy [23] combined a dynamic programming algorithm with a random key-based representation genetic algorithm to minimize $L_{\mathit{max}}$ on a single batch-processing machine in the presence of job available time. Malve and Uzsoy [24] considered the problem for minimizing $L_{\mathit{max}}$ on parallel identical batch-processing machines with dynamic job arrivals. They developed a family of iterative improvement heuristics and combined them with a genetic algorithm. For a further review of the BPM problem, refer to Mathirajan and Sivakumar [1].

In this paper, we address the problem of minimizing $C_{\mathit{max}}$ on a single batch-processing machine with dynamic job arrivals as well as arbitrary job sizes ($1|r_j,s_j,B|C_{\mathit{max}}$). This kind of issue is more important and practical. To date, this problem has not been investigated extensively in the literature. This problem is strongly NP-hard, since $1|s_j,B|C_{\mathit{max}}$ is strongly NP-hard [16]. To the best of our knowledge, only Chou et al. [25] proposed a genetic algorithm to decide the sequence of jobs and then to group the jobs into batches using the first-fit longest processing time (FFLPT) heuristic. This type of approach, employing a meta-heuristic such as a simulated annealing (SA) [17], or a genetic algorithm (GA) [25] to determine a job sequence first, and then applying a simple heuristic or other methods to determine batches, has been applied to solve the BPM problem by many researchers. However, because this type of approach cannot constitute batches directly with the meta-heuristic employed, its performance is very limited by the efficiency of the heuristic or other methods selected. Thus using this method to solve the BPM problem may lead to a bottleneck. In this paper, we chose a different meta-heuristics, ant colony optimization (ACO), to solve this problem. Because ACO is a constructive algorithm [26], it is able to construct batches directly and thus to develop the ACO's optimization ability sufficiently. Details are given in Section 5.

The paper is organized as follows: In the next section, we define the notations and present the mixed integer programming model for the problem. Section 3 investigates a modified version of an existing lower bound on the optimal value of $C_{\mathit{max}}$. Section 4 reviews the heuristic addressed in the literature and deals with the developed heuristic approach for this problem. Section 5 presents the proposed ant colony optimization algorithm with candidate list strategy. Section 6 evaluates and compares the performance of the proposed approaches with benchmark algorithms and CPLEX, an optimization software package. Finally, the conclusions are given.