تغییر الگوریتم مصنوعی کلونی زنبور عسل برای پذیرش سفارش گردش کار دو دستگاه

We consider a two-stage make-to-order production system characterized by limited production capacity and tight order due dates. We want to make joint decisions on order acceptance and scheduling to maximize the total net revenue. The problem is computationally intractable. In view of the fact that artificial bee colony algorithm has been shown to be an effective evolutionary algorithm to handle combinatorial optimization problems, we first conduct a pilot study of applying the basic artificial bee colony algorithm to treat our problem. Based on the results of the pilot study and the problem characteristics, we develop a modified artificial bee colony algorithm. The experimental results show that the modified artificial bee colony algorithm is able to generate good solutions for large-scale problem instances.

In many industries product requirements for customers are customized and unique. As a result, firms in such industries often adopt the make-to-order approach to production. Given tight delivery requirements and limits on production capacity, both order acceptance decision and production scheduling decision need to be taken into account. Selecting the right orders to accept depends on the strategic direction of the firm and many other considerations. From a problem-oriented perspective, order acceptance should go along with a careful analysis of capacity utilization so as to maximize the profit to the firm. In this paper we consider the problem in a two-stage production environment. Each order has distinct product characteristics and is thus described as a job with different processing times in stages 1 and 2. The model is motivated by many industries where the process to produce products typically comprises two consecutive stages, e.g., a processing stage followed by a testing stage. An example is a manufacturer of equipment products that produces large special-purpose pressure vessels. Each order typically includes only one equipment product with distinct characteristics in terms of material, size, and shape, technological process standards, pressure performance index, and so on. It is common that processing a product is time-consuming at one stage but not at the other, i.e., the manufacturing bottleneck stage is not static but depends on all the processed orders. So scheduling is an important issue. On the other hand, any delay in delivering an order beyond its due date may incur a penalty cost to the firm. Operating in such an environment, the firm faces the problem of order acceptance and scheduling in a two-machine flowshop to maximize the total net revenue. The research on taking order acceptance decisions and scheduling decisions into account at the same time has received increasing attention in recent years. The study results mainly consider order acceptance and production in a single machine environment with various settings. Slotnick and Morton (1996) and Ghosh (1997) are regarded as pioneers in studying the order acceptance and scheduling problem. They consider the order acceptance and scheduling decisions at the same time so as to maximize the total revenue. Lewis and Slotnick (2002) extend the problem to multiple periods for the case where rejecting an order of a customer will lead to the loss of all the future orders from that customer. In recent years, research on this topic is further extended to studying problems with different objectives and in various settings. In terms of the solution approaches used to tackle the problem, Slotnick and Morton (2007), Oğuz et al. (2010), and Nobibon and Leus (2011) develop myopic heuristics and exact approaches such as branch-and-bound algorithm, dynamic programming, mixed integer linear programming formulation, and so on. However, the exact algorithms only can solve the small-scale problem since these problems are NP-hard. Recently, Rom and Slotnick (2009) and Cesaret et al. (2012) develop meta-heuristics that apply the techniques of computational intelligence to tackle the problem. The former team proposes genetic algorithms and the latter team designs a tabu search algorithm. Both teams show that their meta-heuristics outperform the myopic heuristics and can obtain optimal or near-optimal solutions for large-scale problem instances. More details on this topic can be found in the recent reviews by Keskinocak and Tayur (2004), and Slotnick (2011). A special case of our problem where all the orders are accepted and processed is the two-machine flowshop scheduling problem to minimize the total weighted tardiness. This case is NP-hard in strong sense (see, e.g., Pinedo (2002)). For the case of the total tardiness problem in m-machine flowshops, Onwubolu and Mutingi (1999) propose a genetic algorithm. For two-machine flowshops, Schaller (2005) propose a branch-and-bound algorithm to solve small-size problem instances optimally. For the case of the total weighted tardiness problem in m-machine flowshops, Parthasarathy and Rajendran (1998), and Rajendran and Ziegler (2003) propose simulated annealing algorithms and improving heuristics, respectively. Detail research on the (weighted) tardiness problem in flowshops can be found in Vallada et al. (2008). As the best of our knowledge, only Rom and Slotnick (2009) and Cesaret et al. (2012) propose meta-heuristics to solve the order acceptance and scheduling problem. We notice that the artificial bee colony (ABC) algorithm is a fairly new meta-heuristic proposed by Karaboga (2005), which is based on simulating the foraging behavior of honeybee swarms. Using some classic benchmark functions, Karaboga and Basturk, 2007, Karaboga and Basturk, 2008 and Karaboga and Basturk, 2009 compare the performance of the ABC algorithm with that of other population-based algorithms such as differential evolution, particle swarm optimization, and evolutionary algorithm, and so on. Their research results demonstrate that the ABC algorithm is comparable to other population-based algorithms and the ABC algorithm on average shows good performance. Furthermore, Gao and Liu (2012) propose a modified ABC algorithm and show that it is superior to the basic ABC algorithm for 28 tested mathematical benchmark functions. Since its invention in 2005, the ABC algorithm has been applied to deal with practical combinatorial optimization problems (see, e.g., Singh, 2009, Kang et al., 2009 and Samrat et al., 2010). Szeto et al. (2011) provide an enhanced ABC algorithm to treat the capacitated vehicle routing problem (CVRP). They show that the algorithm performs better than some of the meta-heuristics (see, e.g., Toth and Vigo, 2003, Berger and Barkoui, 2003 and Ai and Kachitvichyanukul, 2009). Since the problem under study is evidently NP-hard, only small-size instances can be optimally solved within a reasonable time. In view of the good performance of the ABC algorithm and its enhanced version in handling difficult combinatorial optimization problems such as the classical CVRP, we design variants of the ABC algorithm to treat the problem under study. The paper is organized as follows. In Section 2, we give a formal description of the problem under study. In Section 3, we apply the basic ABC algorithm to solve our problem. In Section 4, we propose a modified ABC algorithm based on investigating the problem structure and optimal properties. In Section 5, we show the experimental results of the proposed ABC algorithms. Section 6 concludes our study with a summary.

In this paper we develop a modified ABC algorithm for solving the integrated order acceptance and two-machine flowshop scheduling problem. The objective is to maximize the total net revenue. We first conduct a pilot study on applying the basic ABC algorithm to solve the problem with a view to obtaining clues to design some improving techniques and to properly set the parameters. We then develop a modified ABC algorithm for solving the problem under study. The experimental results show that the modified ABC algorithm can produce good solutions quickly. The research results suggest that the enhanced ABC algorithm is capable of solving large-scale optimization problems that combine production scheduling with other operational decisions.