A tabu search algorithm for the relocation problem in a warehousing system

Relocation of items in a warehousing system is usually used when the handling machines become the bottleneck. This paper addresses the optimization problem of relocation in a warehouse with dynamic operating policy. An integer linear programming formulation is proposed. A two-stage heuristic method is developed to generate an initial solution. A tabu search algorithm is proposed to improve the solution. Two relocation policies are studied and their performances are compared.     

A tabu search approach for cell scheduling problem with makespan criterion

Scheduling problem in a cellular manufacturing system is treated as the group scheduling problem, assuming that intercellular moves can be eliminated by duplicating machines. However, in a typical CMS, duplicating bottleneck machines may be costly and infeasible. This fact limits the applicability of group scheduling. Scheduling problem in the presence of bottleneck machines is termed as cell scheduling. A mixed-integer linear programming model is proposed for the attempted cell scheduling problem and a nested application of tabu search approach is investigated in this paper to solve the problem heuristically. The effectiveness of the proposed nested tabu search (NTS) algorithm is evaluated on 16 problems selected from the literature. Comparison of the results of NTS with SVS-algorithm reveals the effectiveness and efficiency of the proposed algorithm.     

Tabu search for minimizing total tardiness in a job shop

This paper presents a tabu search approach to minimize total tardiness for the job shop scheduling problem. The method uses dispatching rules to obtain an initial solution and searches for new solutions in a neighborhood based on the critical paths of the jobs. Diversification and intensification strategies are suggested. For small problems the solutions’ quality is evaluated against optimal solution values and for large problems the tabu search performance is compared with two heuristics proposed in the literature.     

基于遗传禁忌算法的任务分配与调度的研究

任务分配与调度问题是公认的NP问题,为了合理的对备份任务进行分配与调度,使得最短时间内完成备份任务, 提出了基于遗传禁忌搜索的备份任务调度算法。 重点研究了遗传算法和禁忌搜索算法,并针对二者的不足,提出将其两种算法混合,相互取长补短,仿真实验结果和实例应用表明,笔者提出的算法其搜索效率比单一的遗传算法具有较好的效果。     

A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems—A case study for solar cell industry

This paper studies a solar cell industry scheduling problem which is similar to the traditional hybrid flow shop scheduling (HFS). In a typical HFS with parallel machines problem, the allocation of machine resources for each order should be scheduled in advance and then the optimal multiprocessor task scheduling in each stage could be determined. However, the challenge in solar cell manufacturing is the number of machines can be dynamically adjusted to complete the job within the shortest possible time. Therefore, the paper addresses a multi-stage HFS scheduling problem with characteristics of parallel processing, dedicated machines, sequence-independent setup time, and sequence-dependent setup time. The objective is to schedule the job production sequence, number of sublots, and dynamically allocate sublots to parallel machines such that the makespan time is minimized. The problem is formulated as a mixed integer linear programming (MILP) model. A hybrid approach based on the variable neighborhood search and particle swarm optimization (VNPSO) is developed to obtain the near-optimal solution. Preliminary computational study indicates that the developed VNPSO not only provides good quality solutions within a reasonable amount of time but also outperforms the classic branch and bound method and the current industry heuristic practiced by the case company.     

Constraint programming for project-driven manufacturing

Project-driven manufacturing, based on the make-to-order or the build-to-order principle and predominant in small and medium-size enterprises (SMEs), calls for an efficient solution of large combinatorial problems, especially in such areas as task scheduling or resource management. This paper addresses the problem of finding a computationally effective approach to scheduling a new project subject to constraints imposed by a multi-project environment. A constraint programming (CP) modeling framework is discussed in the context of an efficient decomposition of the constraint satisfaction problem (CSP) and the evaluation of strategies for pruning the search tree. The proposed approach is illustrated through examples of its application to the evaluation of a new production order.     

Coordinated supply chain scheduling

A mixed integer programming approach is proposed for a long-term, integrated scheduling of material manufacturing, material supply and product assembly in a customer driven supply chain. The supply chain consists of three distinct stages: manufacturer/supplier of product-specific materials (parts), producer where finished products are assembled according to customer orders and a set of customers who generate final demand for the products. The manufacturing stage consists of identical production lines in parallel and the producer stage is a flexible assembly line. The overall problem is how to coordinate manufacturing and supply of parts and assembly of products such that the total supply chain inventory holding cost and the production line start-up and parts shipping costs are minimized. A monolithic approach, where the manufacturing, supply and assembly schedules are determined simultaneously, is compared with a hierarchical approach. Numerical examples modeled after a real-world integrated scheduling in a customer driven supply chain in the electronics industry are presented and some computational results are reported.     

Quantized Hopfield networks and tabu search for manufacturing cell formation problems

The use of neural networks in the design of cellular manufacturing system is not new. This paper presents an application of modified Hopfield neural networks in order to solve cell formation problems: the quantized and fluctuated Hopfield neural networks (QFHN). This kind of Hopfield network combined with the “tabu search” approach were primarily used in a hybrid procedure in order to solve the cell formation for big sizes industrial data set. The problem is formulated as a 0/1 linear and integer programming model in order to minimize the dissimilarities between machines and/or parts. Our hybrid approach allows us to obtain optimal or nearly optimal solutions very frequently and much more quickly than traditional Hopfield networks. It is also illustrated that the fluctuation associated with this quantization may enable the network to escape from local minima, to converge to global minima, and consequently to obtain optimal solutions very frequently and much more quickly than pure quantized Hopfield networks (QHN). The effectiveness of the proposed approach is flexibility it gives us, for example, in time problem-solving for large-scale and speed of execution when we apply it.     

A coevolutionary algorithm for the flexible delivery and pickup problem with time windows

This paper addresses a flexible delivery and pickup problem with time windows (FDPPTW) and formulates the problem into a mixed binary integer programming model in order to minimize the number of vehicles and to minimize the total traveling distance. This problem is shown to be NP-hard. In this study, therefore, a coevolutionary algorithm incorporated with a variant of the cheapest insertion method is developed to speed up the solution procedure. The FDPPTW scheme overcomes the shortcomings of the existing schemes for the delivery and pickup problems. By testing with some revised Solomon's benchmark problems, the computational results have shown the efficiency and the effectiveness of the developed algorithm.     

Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families

Motivated by a bottleneck operation in a multi-layer ceramic capacitor production line, we study a scheduling problem of batch processing machine in which a number of jobs are processed simultaneously as a batch. The performance measures considered include makespan, total completion time, and total weighted completion time. We first present a new simple integer programming formulation for the problem, and using this formulation, one can easily find optimal solutions for small problems. However, since the problem is NP-hard and the size of a real problem is very large, we propose a number of heuristic algorithms and design a hybrid genetic algorithm to solve practical big-size problems in a reasonable computational time. To verify performance of the algorithms, we compare them with lower bounds for the problems. From the results of these computational experiments the heuristic algorithms including the genetic algorithm show different performances for the three problems.     

Modeling and optimization of a container drayage problem with resource constraints

This paper investigates the problem faced by firms that transport containers by truck in an environment with resource constraints. The considered area is export-dominant. As a result, there are three types of container movements as inbound full, outbound full, and inbound empty movements. Both the time windows at the terminal and at the customers’ places and the operation times are considered. Empty containers are also regarded as separate transportation resources besides trucks. The total operating time including waiting time of all the trucks in operation is minimized. The problem is first formulated as a directed graph and then mathematically modeled based on the graph. It falls into a multiple traveling salesman problem with time windows (m-TSPTW) with resource constraints. An algorithm based on reactive tabu search (RTS) is developed to solve the problem. A number of randomly generated examples indicate that the algorithm can be applied to the real world.     

A continuous time model for multiple yard crane scheduling with last minute job arrivals

Container terminal (CT) operations are often bottlenecked by slow YC (yard crane) movements. Efficient YC scheduling to reduce the PM waiting time is therefore critical in increasing a CT's throughput. This paper develops an efficient continuous time MILP model for YC scheduling. The model treats realistic operational constraints such as multiple inter-crane interference, fixed YC separation distances, simultaneous container storage/retrievals, realistic YC acceleration/deceleration stages and gantry time, and require far fewer integer variables than previous work. The model significantly improves the solution quality compared to the existing discrete time models and other heuristics found in the literature. Using heuristics and a rolling-horizon algorithm, our model can solve actual container yard (CY) problems quickly and robustly in polynomial time. Also, to cope with the last minute container arrivals which can disrupt routine CT operations, two methods for handling these last minute job insertions are discussed and compared.     

Constraint-based ACO for a shared resource constrained scheduling problem

We consider a scheduling problem arising in the mining industry. Ore from several mining sites must be transferred to ports to be loaded on ships in a timely manner. In doing so, several constraints must be met which involve transporting the ore and deadlines. These deadlines are two-fold: there is a preferred deadline by which the ships should be loaded and there is a final deadline by which time the ships must be loaded. Corresponding to the two types of deadlines, each task is associated with a soft and hard due time. The objective is to minimize the cumulative tardiness, measured using the soft due times, across all tasks. This problem can be formulated as a resource constrained job scheduling problem where several tasks must be scheduled on multiple machines satisfying precedence and resource constraints and an objective to minimize total weighted tardiness. For this problem we present hybrids of ant colony optimization, Beam search and constraint programming. These algorithms have previously shown to be effective on similar tightly-constrained combinatorial optimization problems. We show that the hybrid involving all three algorithms provides the best solutions, particularly with respect to feasibility. We also investigate alternative estimates for guiding the Beam search component of our algorithms and show that stochastic sampling is the most effective.     

A tabu search heuristic for redesigning a multi-echelon supply chain network over a planning horizon

This paper addresses the problem of redesigning a supply chain network with multiple echelons and commodities. The problem belongs to a comprehensive class of network redesign problems previously introduced in the literature. Redesign decisions comprise the relocation of existing facilities to new sites under an available budget over a finite time horizon, the supply of commodities by upstream facilities, the inventory levels at storage facilities, and the flow of commodities through the network. The problem is modeled as a large-scale mixed-integer linear program. Feasible solutions are obtained by using a tabu search procedure that explores the space of the facility location variables. The latter prescribe the time periods in which changes in the network configuration occur. They are triggered by the setup of new facilities, which operate with capacity transferred from the existing facilities, and by closing the latter upon their entire relocation. As the problem is highly constrained, infeasible solutions with excess budget are allowed during the course of the search process. However, such solutions are penalized for their infeasibility. Computational experiments on realistically sized randomly generated instances indicate that this strategic oscillation scheme used in conjunction with tabu search performs very well.     

A multi-objective robust optimization model for multi-product multi-site aggregate production planning in a supply chain under uncertainty

Manufacturers need to satisfy consumer demands in order to compete in the real world. This requires the efficient operation of a supply chain planning. In this research we consider a supply chain including multiple suppliers, multiple manufacturers and multiple customers, addressing a multi-site, multi-period, multi-product aggregate production planning (APP) problem under uncertainty. First a new robust multi-objective mixed integer nonlinear programming model is proposed to deal with APP considering two conflicting objectives simultaneously, as well as the uncertain nature of the supply chain. Cost parameters of the supply chain and demand fluctuations are subject to uncertainty. Then the problem transformed into a multi-objective linear one. The first objective function aims to minimize total losses of supply chain including production cost, hiring, firing and training cost, raw material and end product inventory holding cost, transportation and shortage cost. The second objective function considers customer satisfaction through minimizing sum of the maximum amount of shortages among the customers’ zones in all periods. Working levels, workers productivity, overtime, subcontracting, storage capacity and lead time are also considered. Finally, the proposed model is solved as a single-objective mixed integer programming model applying the LP-metrics method. The practicability of the proposed model is demonstrated through its application in solving an APP problem in an industrial case study. The results indicate that the proposed model can provide a promising approach to fulfill an efficient production planning in a supply chain.     

A hybrid artificial bee colony algorithm for the job shop scheduling problem

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.     

Optimization analysis of supply chain scheduling in mass customization

How to deal with the contradiction between scale production effect and customized demand is the key problem on studying mass customization (MC). When MC is operating in supply chain environment, on one hand, the excellent operating character of the supply chain will give conditions for solving this problem. On the other hand, it will bring out several complicated contradictions and increase the difficulties of the analysis and research on the supply chain operating and scheduling, so it is important to settle the contradictions. Based on our earlier work, the dominant contradictions of the supply chain scheduling in MC and the ways to relieve them are briefly summarized in this paper. A dynamic and multi-objective optimization mathematical model and the appropriate solving algorithm are set up by introducing these relieving methods into the operating process. It is pointed out that the characteristics of the model and algorithm cannot only reflect the unique operating requirements for this special production mode, but also merge with the thought of relieving the dominant contradictions. The feasibility of the model and algorithm in practical application to improve the scheduling efficiency and to settle the key problem mentioned above ultimately gets validated through the analysis of an application case we followed and through the algorithm simulation of a numerical scheduling case.     

太阳能小屋光伏电池的优化铺设

为达到小屋的全年太阳能光伏发电总量尽可能大,而单位发电量的费用尽可能小,建立多目标规划模型,采用平面二分搜索启发式算法,根据最小浪费优先策略对光伏电池进行铺设,得到墙面铺设光伏电池的种类和数量,算出电池板的最佳倾角。     

Economic lot and delivery scheduling problem for multi-stage supply chains

The economic lot and delivery scheduling problem for a multi-stage supply chain comprising multiple items is studied in this paper. It is required to develop a synchronized replenishment strategy, and specify the sequence of production and the replenishment cycle time that achieves synchronization through the supply chain at minimum cost. The problem is presented in a novel formulation based on the quadratic assignment representation. The common cycle time and the integer multipliers policies are adopted to accomplish the desired synchronization. The two policies are represented by nonlinear models handled through a hybrid algorithm. The algorithm combines linearization, outer approximation and Benders decomposition techniques. Results of the two policies demonstrate that a cost reduction up to16.3% can be attained by employing the integer multipliers policy instead of the common cycle time. Computational experiments show the efficiency of the new formulation and solution algorithm by reaching the optimal solution for large problem instances in short time.     

A branch and bound algorithm for sub-contractor selection in agile manufacturing environment

Partnership and partner selection play a key role for “Opportunity Driven” project contractors in agile manufacturing environment. In this paper, we present an investigation on the partner selection problems with engineering projects. Firstly, the problem is described by a 0–1 integer programming with non-analytical objective function. It is proven that the partner selection problem is a type of earliness and tardiness production planning problems. By introducing the concepts of inefficient and ideal candidates, we propose the theory of solution space reduction which can efficiently reduce the complexity of the problem. Then, a branch and bound algorithm embedded project scheduling is developed to obtain the solution. The approach was demonstrated by the use of an experimental example drawn from a construction project of coal fire power station. The computational results have been found to be satisfactory.