بهینه سازی کلونی مورچه ها بهبود یافته برای برنامه ریزی ماشین آلات یکسان موازی با اندازه های شغلی دلخواه

In this paper we consider the problem of scheduling parallel batching machines with jobs of arbitrary sizes. The machines have identical capacity of size and processing velocity. The jobs are processed in batches given that the total size of jobs in a batch cannot exceed the machine capacity. Once a batch starts processing, no interruption is allowed until all the jobs are completed. First we present a mixed integer programming model of the problem. We show the computational complexity of the problem and optimality properties. Then we propose a novel ant colony optimization method where the Metropolis Criterion is used to select the paths of ants to overcome the immature convergence. Finally, we generate different scales of instances to test the performance. The computational results show the effectiveness of the algorithm, especially for large-scale instances.

The problem of scheduling batching machines with arbitrary job sizes is often encountered in real industries. The typical applications are semiconductor manufacturing, food processing, metal working and ship scheduling at navigation locks. In the burn-in operation of semiconductor manufacturing, the chips have different sizes and processing times which are both required by the customers. The actual processing time of a chip can be longer than or equal to the required time, however, it cannot be shorter than the required time. The chips are processed in batches where a batch means a subset of chips. A burn-in oven has a limited capacity, i.e., the total size of jobs in a batch cannot exceed the capacity. During the burn-in operation, the oven is heated to a high temperature. Therefore, the operation cannot be interrupted until all the chips in a batch are completed. After the burn-in operation, the defective ones can be found and eliminated to guarantee the quality of products. Such applications are also encountered in food processing, metal working industries and ship scheduling at navigation locks. In the related research, the scheduling problem of batching machines was proposed by Lee et al. [1]. They investigated the scheduling where a batching machine can process a fixed number of jobs and showed that the problem of minimizing makespan is NP-hard in the strong sense. Janiak et al. [2] and [3] and Bellanger et al. [4] proposed algorithm for minimizing total completion time. Then the scheduling of a single batching machine with agreeable release times and due dates was proposed from the semiconductor manufacturing systems [5]. Then Jolai [6] investigated several algorithms for the single machine problem. Ji and Cheng [7] and Li et al. [8] considered the scheduling of batching machines with deteriorating jobs and release dates and provided polynomial time algorithms. Janiak et al. [9] and [10] considered the single-machine problems with resource dependent times and limited deterioration of reworkables. The two-machine shop problems were studied in Potts et al. [11] where the machines can process a bounded or unbounded number of jobs. On the other hand, the problem of scheduling batching machines with arbitrary job sizes was introduced by Uzsoy [12]. The single-machine problem was investigated and heuristic methods were proposed to minimize makespan and total completion times respectively. Then the performances of the proposed heuristics were analysed by Zhang et al. [13], where an improved 7/4-approximation algorithm was proposed for minimizing makespan. Dupont and Flipo [14] introduced a branch and bound method for the problem. Kashan et al. [15] considered a general version of the single-machine problem, in which the processing times of the jobs with sizes greater than 1/m is not less than the other ones, where m ≥ 2 and is an integer. They proposed an algorithm with absolute worst-case ratio of 3/2 and asymptotic worst-case ratio of (1 + 1/m). Cheng et al. [16] studied the fuzzy uncertainty in the real manufacturing and proposed a fuzzy model for single-machine problem. The single-machine problem with release time was studied in Ref. [17] and a (2 + ɛ)-approximation algorithm was designed, where ɛ > 0 and can be arbitrarily small. In recent years, meta-heuristic algorithms have been introduced to solve single-machine problems. Sevaux and Peres [18] applied genetic algorithm to minimize the weighted number of late jobs. Kashan et al. [19] and Damodaran et al. [20] modified the coding and decoding methods to improve the quality of the solutions. Other meta-heuristic algorithms have also been applied in the problem like simulated annealing [21] and branch and price algorithm [22]. In the research of multi-machine problems, Jula and Leachman [23] considered the coordination problem in supply chain where the production facility has batching machines. Ant colony optimization (ACO) is a typical meta-heuristic algorithm inspired by the real ants’ behaviour of searching food in nature. The algorithm was introduced by Dorigo et al. [24]. For it is simple to implement and it has a good performance in optimization, ACO has been widely used in combinatorial optimization problems, such as structural topology optimization [25], shortest path problem [26], Bayesian networks [27] and scheduling problems [28]. The readers can refer to Ref. [29] for a brief survey of the application of ACO. However, the determinate selection of paths for ants tends to immature convergence [30]. In the implementation of ACO, the paths of ants are generated according to two factors: the pheromone value of paths and the heuristic information of paths. The pheromone on a path is strengthened if it is selected by an ant and consequently, the behaviour of ants in the earlier iterations influences the ones in the later iterations. When the earlier ants concentrate on locally optimal paths, the pheromone on these paths will be reinforced repeatedly, which has a negative impact on the final solutions. In order to overcome the disadvantage, we use the stochastic selection mechanism of the Metropolis Criterion and propose a novel ACO in this paper. In the early iterations, the restriction is relaxed for the paths. More paths are selected as elite ones. In the later evolution of the algorithm, the restriction is tightened gradually and is controlled by the Metropolis Criterion. Then the effectiveness of the algorithm is tested by instances in the experiments. The remainder of the paper is organized as follows. In Section 2, we describe the problem and present a mathematical model. In Section 3, we show the properties of optimal solutions and feasible solutions. In Section 4, we propose our algorithm and show the detailed implementation. In Section 5, we show the design of instances and report the computational results. Finally in Section 6, we conclude this paper and give future directions.

In this paper, we investigate the problem of scheduling parallel batching machines with arbitrary job sizes. The machines have identical capacity to accommodate jobs and identical processing velocity. The processing of a batch is non-preemptive. The objective is to minimize makespan. We present a mixed integer programming model of the problem and derive properties on solutions. Then we provide a novel ant colony optimization for the problem. The selection mechanism of elite paths is modified by using the Metropolis Criterion. We introduce the implementation of the algorithm and report the experimental results. By comparing the results of the algorithm with other algorithms in current literature, we show the effectiveness of the proposed algorithm. In future research, optimal algorithms need to be investigated, for example, the dynamic programming method. Polynomial time accurate algorithms with performance guarantees also deserve more research. For the problem is more complex than classical parallel machine scheduling problems, other intelligent algorithms are also of interest given that the performance and running time can be improved. Besides the research on optimization algorithms, the scheduling problems with other machine configurations like open shop and job shop are of interest. Problems with other objective functions also deserve more research.