الگوریتم مصنوعی کلونی زنبور عسل گسسته برای برنامه ریزی جریان بار مسئله فروشگاه

In this paper, a discrete artificial bee colony (DABC) algorithm is proposed to solve the lot-streaming flow shop scheduling problem with the criterion of total weighted earliness and tardiness penalties under both the idling and no-idling cases. Unlike the original ABC algorithm, the proposed DABC algorithm represents a food source as a discrete job permutation and applies discrete operators to generate new neighboring food sources for the employed bees, onlookers and scouts. An efficient initialization scheme, which is based on the earliest due date (EDD), the smallest slack time on the last machine (LSL) and the smallest overall slack time (OSL) rules, is presented to construct the initial population with certain quality and diversity. In addition, a self adaptive strategy for generating neighboring food sources based on insert and swap operators is developed to enable the DABC algorithm to work on discrete/combinatorial spaces. Furthermore, a simple but effective local search approach is embedded in the proposed DABC algorithm to enhance the local intensification capability. Through the analysis of experimental results, the highly effective performance of the proposed DABC algorithm is shown against the best performing algorithms from the literature.

Flow shop scheduling problem is one of the most popular machine scheduling problems with extensive engineering relevance, representing nearly a quarter of manufacturing systems, assembly lines, and information service facilities in use nowadays [13], [19], [26] and [27]. In a traditional flow shop scheduling, a job is indivisible and it cannot be transferred to the next machine before its processing is finished [17] and [18]. However, this may not be the case in many practical situations where a job consists of many identical items. In order to reduce machine waiting time, a job is allowed to be overlapping its operations between successive machines by splitting it into a number of smaller sublots [29]. The job splitting into sublots process is usually called lot-streaming, which is one of the effective techniques used to implement the time-based strategy in today’s era of global competition [3]. Through the extensive use of just-in-time (JIT) system in manufacturing, the performance measure related to both earliness and tardiness penalties has raised significant attention [23]. For this reason, this paper aims at solving an n-job, m-machine lot-streaming flow shop scheduling problem with equal size sublots to minimize the total weighted earliness and tardiness penalties. We consider two different cases, namely, the idling case and no-idling case. The no-idling case is the one where there is no-idling production interruption time (i.e., the idle time) between any two adjacent sublots at the same stage, whereas the idling case allows idle time on machines [3]. A comprehensive review of scheduling problems involving lot-streaming can be found in [3]. The lot-streaming flow shop scheduling problems can be classified into two categories, i.e., single-job and multi-job problems. For the first category, the main goal is to find the optimal sublot sizes. A flow shop with makespan criterion is considered in [17] indicating that it is sufficient in a single-job model to use the same sublot sizes for all machines. Regarding total flowtime minimization, optimal sublot size policies and two heuristic methods are given for a single job in a flow shop by Kropp and Smunt [11]. Bukchin et al. [1] proposed the optimal solution properties and developed a solution procedure for solving a two-machine flow shop scheduling problem with the total flow time criterion where sublot detached setups and batch availability were considered. For the second category, the primary purpose is to simultaneously obtain the best sublot allocation, i.e., sublot starting and completion times, and the best job sequence. For this propose, Vickson and Alfredsson [24] studied the effects of transfer batches in the two-machine and special three-machine problems with unit-size sublots. Cetinkaya [2] proposed an optimal transfer batch and scheduling algorithm for a two-stage flow shop scheduling problem with setup, processing and removal times separated. Vickson [25] examined a two-machine lot-streaming flow shop problem involving setup and sublot transfer times with respect to both continuous and integer valued sublot sizes. Sriskandarajah and Wagneur [22] devised an efficient heuristic for solving the problem of simultaneous lot-streaming and scheduling of multiple products in a two-machine no-wait flow shop. For the m-machine flow shop scheduling problems, Kumar et al. [12] extended the approach in Sriskandarajah and Wagneur [22] to an m-machine case. Kalir and Sarin [4] presented a bottleneck minimal idleness (BMI) heuristic to sequence a set of batches to be processed in equal sublots for minimizing makespan. Recently, Marimuthu et al. [15] proposed a genetic algorithm (GA) and hybrid genetic algorithm (HGA) for an m-machine flow shop with makespan and total flow time criteria. More recently, ant colony optimization (ACO) and threshold accepting (TA) algorithms were presented for solving the same problem by Marimuthu et al. [16]. As mentioned before, with the advent and development of JIT manufacturing systems, efforts have been focused on minimizing the total weighted earliness and tardiness penalties for the m-machine lot-streaming flow shop scheduling problems. Yoon and Ventura [29] presented a procedure where a linear programming (LP) formulation was designed to obtain optimal sublot completion times for a given sequence and sixteen pairwise interchange methods were utilized to search for the best sequence. Later on, Yoon and Ventura [28] proposed a hybrid genetic algorithm (HGA) by incorporating the LP and a pairwise interchange method into the traditional genetic algorithm. More recently, Tseng and Liao [23] developed a discrete particle swarm optimization (DPSO), where a net benefit of movement (NBM) algorithm was utilized to obtain the optimal allocation of the sublots for a given sequence, and the objective function values obtained by the NBM heuristic are used to guide the search towards the best sequence. In these three recent literatures, only the idling case is addressed. To the best of our knowledge, there is no published paper for dealing with the lot-streaming flow shop with total earliness and tardiness criterion with respect to the no-idling production interruption time between any two adjacent sublots. In general, swarm intelligence is based on collective behavior of self-organized systems. As a typical example of swarm intelligence, the bee swarming around her hive has received significant interest from researchers. Recently, by modeling the specific intelligent behaviors of honey bee swarms, an artificial bee colony (ABC) algorithm is developed by Karaboga [9] to optimize multi-variable and multi-modal continuous functions. Numerical comparisons demonstrated that the performance of the ABC algorithm is competitive to other population-based algorithm with an advantage of employing fewer control parameters [6], [7], [8], [9] and [10]. Due to its simplicity and ease of implementation, the ABC algorithm has captured much attention and has been applied to solve many practical optimization problems [5], [6] and [21]. Since there is no published work to deal with the lot-streaming flow shop problem by using the ABC algorithm, we present a novel discrete ABC (DABC) algorithm for solving the lot-streaming flow shop problem with a criterion of total weighted earliness and tardiness penalties. Furthermore, both no-idling case and idling case between any two adjacent sublots of a job at the same stage are considered, respectively. As in Yoon and Ventura [28] and Tseng and Liao [23] we assume equal size sublots and infinite capacity buffers, and divide the problem solving process into two closely dependent phases. In the first phase, the NBM heuristic developed by Tseng and Liao [23] is used to determine the optimal sublot allocations for a given sequence. In the second phase, the proposed DABC algorithm is applied to find the best sequence in the entire region. Computational experiments and comparisons show that the proposed DABC algorithm outperforms the two recent best performing algorithms for solving the lot-streaming flow shop scheduling problem with the total weighted earliness and tardiness criterion. The rest of the paper is organized as follows. In Section 2, the lot-streaming flow shop scheduling problem with equal size sublots is formulated. In Section 3, the basic ABC algorithm is introduced. Section 4 describes the basic components of DABC algorithm whereas the computational results and comparisons are described in Section 5. Finally, Section 6 presents the concluding remarks.

This paper aimed at minimizing total weighted earliness and tardiness penalties for the lot-streaming flow shop scheduling problems with equal sized sublots. We examined the problem under both the idling and no-idling cases and proposed a novel discrete artificial bee colony (DABC) algorithm. To the best of our knowledge, this was the first reported application of the ABC algorithm for solving the problem under consideration. In the proposed algorithm, the food sources were represented as discrete job permutations. The ABC-based searching mechanism with an effective population initialization approach and a self-adaptive neighboring food source generation strategy were developed to perform exploration for promising solutions within the entire solution space. Furthermore, a simple but effective local search algorithm was employed to further exploit the best solution. Due to the reasonable hybridization of the ABC search and local search, the proposed DABC algorithm had the ability to obtain good results for the lot-streaming flow shop scheduling problems with total weighted earliness and tardiness criterion. Computational simulations and comparisons demonstrated the effectiveness and efficiency of the proposed DABC algorithm. Our future work is to investigate the other meta-heuristics for the lot-streaming flow shop problem and generalize the application of the ABC algorithms to solve other combinatorial optimization problems.