مسئله برنامه ریزی دو هدفه در ماشین آلات دسته ای از طریق یک سیستم کلونی مورچه ها مبتنی بر رویکرد "پاره تو"

This research aims to minimize the bi-criteria of makespan and maximum tardiness on a set of identical batch-processing machines arranged in parallel. Each machine can process multiple jobs simultaneously as long as the machine capacity is not exceeded. Each job is defined by its processing time, ready time, due date, and size. The processing time and ready time of a batch are represented by the largest processing time and release time among all jobs in the batch, respectively. For this problem, a scheduling algorithm based on the framework of a multi-objective ant colony optimization (MOACO) approach called a Pareto-based ant colony system (PACS) was developed. Based on the constructive characteristics of PACS, a new mechanism of solution construction was introduced so that the proposed algorithm had the ability to explore the entire solution space. Moreover, corresponding to the new construction mechanism, a candidate list strategy and a form of dynamic heuristic information were developed to reduce the search space and direct the search toward the promising regions, respectively. Through extensive computational experiments with various problem instances, the effectiveness of the proposed algorithm was evaluated by measuring the computational efficiency and solution quality. The experiment results demonstrated that PACS had a superior performance compared to other benchmark algorithms, especially for large job instances.

Nowadays microprocessors, memory chips, and other semiconductor related devices are a part of daily life, appearing in electronics ranging from personal computers to cellular phones. The semiconductor industry has already become one of the largest industries in the world, and semiconductor manufacturers need to utilize their resources effectively to confront the huge demand and severe competition in the marketplace. Furthermore, there is increasing pressure for semiconductor manufacturers to improve their overall performance, such as machine utilization and on-time delivery. Effective scheduling is one of the most economical and executable potential solutions to such challenges. Batch processing is a very common procedure in semiconductor manufacturing for the avoidance of setups and/or facilitation of material handling. A batch is defined as a group of jobs that have to be processed jointly (Brucker et al., 1998) and a batch scheduling problem consists of grouping jobs on each machine into batches which are scheduled either in serial (called s-batching) or in parallel (called p-batching). On an s-batching machine, the processing time of a batch equals the sum of the processing times of all jobs that form the batch. On a p-batching machine, several jobs can be processed as a batch simultaneously, and the length of a batch is the largest processing time of its jobs. In semiconductor manufacturing, p-batching is a much more important issue, occurring in many processes such as oxidation/deposition/diffusion of wafer fabs and the burn-in operation in test facilities (Moench et al., 2011). For instance, the burn-in operation of the final testing phase of semiconductor manufacturing tests the integrated circuits for defects by subjecting them 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. While very important, the operations’ lengthy processing time compared with the other operations in semiconductor manufacturing creates a bottleneck in the final testing phase. Consequently efficient scheduling is of great concern to overall performance. In addition, p-batching is commonly observed in other modern industrial environments, such as in chemical, food and mineral processing, pharmaceutical, and metalworking industries as well as with wafer and environmental stress screening chamber fabrication. This paper focuses on p-batching scheduling, which is also known as the scheduling of a batch-processing machine (BPM) or batch machine in the literature (Mathirajan and Sivakumar, 2006 and Moench et al., 2011). On a BPM, a fixed maximum batch size exists as the capacity of the batch machine, and a batch machine is capable of accommodating a group of jobs simultaneously as long as the sum of the job sizes in the batch is less than or equal to the machine capacity. The processing time of each batch is determined by the longest job processing time among the jobs contained in the batch. Finally, once a batch is being processed, it is non-preemptable during the long period of processing. In this research, we consider the BPM problem of scheduling on identical batch machines arranged in parallel with dynamic job arrivals and non-identical job sizes to minimizing makespan (Cmax) and maximum tardiness (Tmax) simultaneously. Note that the target problem is complicated by the considerations of different constraints and multiple objectives. First, a machine environment involving multiple batch machines instead of one requires an additional decision about machine assignment to obtain a final solution. Secondly, dynamic job arrivals and non-identical job sizes, which reflect realistic conditions in most manufacturing systems, are considered. Lastly, two performance measures of Cmax and Tmax, which are among the most commonly used criteria in the batch scheduling research, are considered. Makespan is a measure of system utilization while maximum tardiness is a measure of performance in meeting customer due dates. This target problem can be denoted by Pm|rj,sj,p-batch|Cmax,TmaxPm|rj,sj,p-batch|Cmax,Tmax, and the details of the problem statement and formulation will be given in Section 3. To the best of our knowledge, the BPM scheduling problem for optimizing multi-objectives has not been fully investigated in the literature. Only Kashan et al. (2010) studied a NP-hard scheduling problem on a BPM while optimizing the same objectives considered in the target problem. However, they do not consider the constraints of dynamic job arrivals and multiple BPMs, which often arises from real-world production systems and occurs in a more general environment. Besides, this then leads to the problem becoming much more complicated and being NP-hard as well. In view of the complexity of the target problem, we extend the framework of ant colony system, which has been proven effective for solving complex single objective optimization problems, to explore its potential for solving multi-objective scheduling problems. The rest of this paper is outlined as follows: Section 2 provides a literature review, including batch machine scheduling problems with different constraints. Section 3 illustrates the problem under study and presents the bi-objective integrated mathematical model for the problem. Section 4 describes the proposed multi-objective ant colony optimization algorithm, which employs several distinctive features based on the problem-specific knowledge. Then, taking into account different test instances and evaluation metrics, we conduct experimental studies as presented in Section 5. The paper concludes in Section 6.

In this paper, we addressed the bi-criteria scheduling problem on a set of BPMs arranged in parallel with non-identical job sizes and dynamic job arrivals for minimizing makespan and maximum tardiness. With the considerations of different constraints and multiple objectives, this problem has a high practical value while it becomes much harder to solve. We proposed a scheduling approach based on the framework of MOACO to solve the target problem. It employed a new solution construction mechanism that considered three decisions (i.e. batch formation, machine assignment, and batch sequencing) simultaneously for encoding a feasible solution that explored the entire solution space. Furthermore, we also developed the suitable components of candidate list and heuristic information corresponding to the new construction mechanism, which could direct the search toward promising regions and provide more precise guidance of the search process. Taking into account different evaluation metrics, computational results showed that the proposed PACS algorithm significantly outperformed the compared algorithms as the number of jobs increased. Future work includes extending our algorithm to the case of BPM scheduling with other constraints and optimization objectives. Also, it is of interest to consider other machine environments, such as flow shop or job shop.