الگوریتم مصنوعی کلونی زنبور عسل ترکیبی برای مسئله زمانبندی کار مغازه

The job shop scheduling problem (JSSP) has attracted much attention in the field of both information sciences and operations research. In terms of the objective function, most existing research has been focused on the makespan criterion (i.e., minimizing the overall completion time). However, for contemporary manufacturing firms, the due date related performance is usually more important because it is crucial for maintaining a high service reputation. Therefore, in this study we aim at minimizing the total weighted tardiness in JSSP. Considering the high complexity, a novel artificial bee colony (ABC) algorithm is proposed for solving the problem. A neighborhood property of the problem is discovered, and then a tree search algorithm is devised to enhance the exploitation capability of ABC. According to extensive computational tests, the proposed approach is efficient in solving the job shop scheduling problem with total weighted tardiness criterion.

The job shop scheduling problem (JSSP) has been known as a very challenging combinatorial optimization problem since 1950s. Because JSSP is NP-hardNP-hard in the strong sense (Lenstra et al., 1977), it is by no means easy to guarantee the optimal solution even for small-scale JSSP instances. In the recent years, meta-heuristics have become extremely popular as practical optimization methods for solving JSSPs. Successful meta-heuristics include but are not limited to genetic algorithm (GA) (Essafi et al., 2008 and Al-Hinai and ElMekkawy, 2011), tabu search (TS) (Vilcot and Billaut, 2011 and Li et al., 2011), particle swarm optimization (PSO) (Sha and Hsu, 2006 and Moslehi and Mahnam, 2011), ant colony optimization (ACO) (Huang, 2010 and Xing et al., 2010) and memetic algorithm (MA) (Lacomme et al., 2012 and Gao et al., 2011). In the standard JSSP, a set of n jobs View the MathML sourceJ={Jj}j=1n are waiting to be processed by a set of m machines View the MathML sourceM={Mk}k=1m under some basic assumptions, the most important of which are listed as follows: (i) Each machine can process at most one job at a time; (ii) Each job can be processed by at most one machine at a time. Each job consists of a group of operations to be performed by each machine in a predetermined order. The duration time of each operation is fixed and known. Besides, a preset due date dj and a preset weight wj are given for each job. Due date is the preferred latest finishing time of a job, so completion after this specific time will result in losses such as a worsened reputation among customers. Weights reflect the level of importance of the orders from different customers, larger values suggesting higher strategic importance. If we use Cj to denote the completion time of job j, the objective function of JSSP can be makespan View the MathML source(Cmax=maxj=1n{Cj}), maximum lateness View the MathML source(Lmax=maxj=1n{Lj}), total tardiness View the MathML source(TT=∑j=1nTj) and total weighted tardiness View the MathML source(TWT=∑j=1nwjTj), where lateness is defined as Lj=Cj−djLj=Cj−dj while tardiness is defined as Tj=max{0,Cj−dj}Tj=max{0,Cj−dj}. Up till now, most research on JSSP has been focused on the makespan criterion. However, due date related performances are becoming more relevant for the firms that adopt the make-to-order (MTO) manufacturing strategy nowadays. Such a firm will first “quote” a due date1 for each order that it receives, and once the due date has been fixed, the firm must make every effort to deliver the products before or on the due date. Late delivery will result in economic losses in various forms. In this sense, the total weighted tardiness measure better reflects the critical factors that affect the profits of a MTO firm. However, we are by no means claiming that other objective functions are unimportant. In fact, when the due dates are not very tight to form harsh constraints, makespan or flowtime can be an important performance measure for production efficiency. Meanwhile, total weighted tardiness is more difficult to optimize than makespan. This can be explained from two aspects. Intuitively, CmaxCmax is determined by the completion time of the (probably unique) bottleneck job while TWT is determined by the completion times of all the tardy jobs. Especially when the due dates are tight, optimizing TWT means the algorithm has to consider a large number of critical paths simultaneously. Making tradeoffs is even more difficult in the case where the weights of jobs are widely different. Therefore, compared with CmaxCmax, the objective function TWT is more sensitive to slight changes in the production schedule, which makes the optimization process more complicated. From the theoretical aspect, the following relationship exists between different objective functions under the same machine environment (Pinedo, 2008): α|β|Cmax∝α|β|Lmax∝α|β|∑Tj∝α|β|∑wjTjα|β|Cmax∝α|β|Lmax∝α|β|∑Tj∝α|β|∑wjTj (following the three-field notation; Jain and Meeran, 1999). “P1∝P2P1∝P2” indicates that problem P1 can be reduced to problem P2, and thus the difficulty of solving P2 is at least the same as that of solving P1. The first reduction relation is straightforward by letting dj=0,∀jdj=0,∀j. The last reduction is also obvious by letting View the MathML sourcewj=1,∀j. For the proof of the second reduction relation, we should notice that View the MathML sourceLmax≤z⇔Cj−(dj+z)≤0,∀j. By letting d′j=dj+zd′j=dj+z and T′j=max{0,Cj−d′j}T′j=max{0,Cj−d′j}, we obtain Lmax≤z⇔∑T′j=0Lmax≤z⇔∑T′j=0. Therefore, TWT includes many other objective functions (e.g. CmaxCmax, LmaxLmax and ∑wjCj∑wjCj) as special cases. The optimization difficulty of TWTTWT is thus higher than these objectives. Below we will use the abbreviation “TWT-JSSP” to denote the job shop scheduling problem with total weighted tardiness objective. The rest of this paper is organized as follows. Section 2 provides a brief review on the existing solution methods for TWT-JSSP and the artificial bee colony algorithm. Section 3 discusses the mathematical model of TWT-JSSP and a neighborhood property. Section 4 describes the design of a new artificial bee colony algorithm for solving TWT-JSSP. Section 5 presents the computational results. Finally, Section 6 concludes the paper.

In this paper, we propose an artificial bee colony algorithm based on problem-dependent local search for the job shop scheduling problem with the objective of minimizing total weighted tardiness. The main contributions can be summarized as follows: (1) We propose new block properties for TWT-JSSP with mathematical proofs. Although the block properties for the makespan criterion are already discovered in early research, up till now they have not been successfully generalized to work under the TWT objective. So our findings of new block properties lay a solid ground for the design of improved local search algorithms. (2) The local search procedure described in this paper is based on a tree-type search pattern. The principle is different from other well-established algorithms like beam search. Instead, the tree is used to explore compound neighborhoods (multiple swaps of operations). Therefore, each node in the tree stands for a complete solution in the neighborhood of its parent rather than a partial solution. Such a local search mechanism is proven to be quite effective for the TWT-JSSP. (3) The proposed block properties have been integrated with the tree search procedure in order to accelerate the convergence of the entire algorithm. Meanwhile, the local search module has been integrated with the ABC algorithm in a coordinated manner. Indeed, the discrete local search has replaced the continuous neighborhood generation method for onlooker bees. This makes ABC considerably more effective for solving the TWT-JSSP. Finally, the computational results verify the effectiveness and efficiency of the proposed approach, especially for larger-scale instances. The future research can be carried out from the following aspects: (1) It is worthwhile to investigate the new and more effective neighborhood properties for TWT-JSSP. This could provide a deeper insight into the inherent nature of TWT-JSSP and facilitate the design of meta-heuristics like ABC. (2) It is worthwhile to consider other encoding schemes and local search mechanisms of the ABC algorithm (such as the discrete ABC, Pan et al., 2011), which may be more suitable for the application of the neighborhood properties.