An innovative artificial bee colony algorithm and its application to a practical intercell scheduling problem

In this article, an innovative artificial bee colony (IABC) algorithm is proposed, which incorporates two mechanisms. On the one hand, to provide the evolutionary process with a higher starting level, genetic programming (GP) is used to generate heuristic rules by exploiting the elements that constitute the problem. On the other hand, to achieve a better balance between exploration and exploitation, a leading mechanism is proposed to attract individuals towards a promising region. To evaluate the performance of IABC in solving practical and complex problems, it is applied to the intercell scheduling problem with limited transportation capacity. It is observed that the GP-generated rules incorporate the elements of the most competing human-designed rules, and they are more effective than the human-designed ones. Regarding the leading mechanism, the strategies of the ageing leader and multiple challengers make the algorithm less likely to be trapped in local optima.     

供应链中生产和运输协调调度问题初探

提出了解决供应链中生产和航空运输协调调度问题的理论框架.基于对生产调度和航空运输调度彼此制约关系的分析,协调调度问题被分解为两个子调度问题.建立了航空运输子调度问题的整数规划模型,并证明了该问题为NP完全问题.提出了基于倒排调度方法(backward scheduling method)的调度算法解单机生产调度子问题.     

Intercell scheduling: A negotiation approach using multi-agent coalitions

Intercell scheduling problems arise as a result of intercell transfers in cellular manufacturing systems. Flexible intercell routes are considered in this article, and a coalition-based scheduling (CBS) approach using distributed multi-agent negotiation is developed. Taking advantage of the extended vision of the coalition agents, the global optimization is improved and the communication cost is reduced. The objective of the addressed problem is to minimize mean tardiness. Computational results show that, compared with the widely used combinatorial rules, CBS provides better performance not only in minimizing the objective, i.e. mean tardiness, but also in minimizing auxiliary measures such as maximum completion time, mean flow time and the ratio of tardy parts. Moreover, CBS is better than the existing intercell scheduling approach for the same problem with respect to the solution quality and computational costs.     

Supply chain optimisation with both production and transportation integration: multiple vehicles for a single perishable product

This paper deals with an extension of the integrated production and transportation scheduling problem (PTSP) by considering multiple vehicles (PTSPm) for optimisation of supply chains. The problem reflects a real concern for industry since production and transportation subproblems are commonly addressed independently or sequentially, which leads to sub-optimal solutions. The problem includes specific capacity constraints, the short lifespan of products and the special case of the single vehicle that has already been studied in the literature. A greedy randomised adaptive search procedure (GRASP) with an evolutionary local search (ELS) is proposed to solve the instances with a single vehicle as a special case. The method has been proven to be more effective than those published and provides shorter computational times with new best solutions for the single vehicle case. A new set of instances with multiple vehicles is introduced to favour equitable future research. Our study extends previous research using an indirect resolution approach and provides an algorithm to solve a wide range of one-machine scheduling problems with the proper coordination of single or multiple vehicles.     

Research on rush order insertion rescheduling problem under hybrid flow shop based on NSGA-III

Rush order insertion is widespread in the enterprises that apply make-to-order production mode which affects the stability of production system. This article studies rush order insertion rescheduling problem (ROIRP) under hybrid flow shop (HFS) with multiple stages and multiple machines. A mathematical model simultaneously considering constraints such as lots, sequence-dependent set-up times and transportation times with objectives to minimise makespan, total transportation time and total machine deviation between the initial scheduling plan and the event-driven rescheduling plan is developed and NSGA-III is applied to solve the problem. Three groups of experiments are carried out which verify the suitability of NSGA-III for HFS scheduling problem with multi-objective and multi-constraint, the effectiveness of NSGA-III for the proposed ROIRP and the feasibility and effectiveness of the proposed model and algorithm in solving the ROIRP of a realistic ship pipe parts manufacturing enterprise.     

Book review of Global Strategic Management,by P. Lasserre,Palgrave Macmillan,Basingstoke, 2003, xx + 454 pp., £24.99, softcover (ISBN 0 333 79375 7)

This paper considers the simultaneous scheduling of material handling transporters (such as automatic guided vehicles or AGVs) and manufacturing equipment (such as machines and workcentres) in the production of complex asembled product. Given the shipping schedule for the end-items, the objective of the integrated problem is to minimize the cumulative lead time of the overall production schedule (i.e. total makespan) for on-time shipment, and to reduce material handling and inventory holding costs on the shop-floor. The problem of makespan minimization is formulated as a transportation integrated scheduling problem, which is NP-hard. For industrial size problems, an effective heuritsic is developed to simultaneouly schedule manufacturing and material handling operations by exploting the critical path of an integrated operation network. The performance of the proposed heuristic is evaluated via extensive numerical studies and compared with the traditional sequential scheduling approach. The superiority of the integrated heuristic is well documented.     

A coordinated algorithm for integrated production scheduling and vehicle routing problem

In this paper, the integrated production scheduling and vehicle routing problem is considered for a Make-to-Order manufacturer, who has a single machine for production and limited vehicles with capacity constraints for transportation. The objective is to determine production scheduling and vehicle routing, which are two interacted decisions, to minimise the maximum order delivery time. A property on optimal production sequence is proposed first, based on which backward and forward batching methods are developed and are embedded into a proposed genetic algorithm. The proposed genetic algorithm is capable of providing high-quality solutions by determining the two decisions simultaneously. For comparison purpose, a two-stage algorithm is developed, which decomposes the overall problem into two successively solved sub-problems. The experiments show that the proposed genetic algorithm can provide higher quality solutions than the proposed two-stage algorithm and two published algorithms studying related problems.     

Integrated production and distribution planning in the fast moving consumer goods industry: a block planning application

In the fast moving consumer goods industry there is an ongoing trend towards an increased product variety and shorter replenishment cycle times. Hence, manufacturers seek a better coordination of production and distribution activities. In this paper, a so-called block planning approach is presented which establishes cyclical production patterns based on the definition of setup families. For the delivery of final goods from the plants to distribution centres two transportation modes are considered, full truckload and less than truckload. The proposed mixed-integer linear optimization model minimizes total production and transportation costs. Numerical results demonstrate the practical applicability of the proposed block planning approach. In particular, a rigid and a flexible block planning approach are compared which differ by their degree of flexibility in the scheduling of the production lots.     

A block transportation scheduling system considering a minimisation of travel distance without loading of and interference between multiple transporters

Material transportation scheduling problems concerning scheduling optimisation have been extensively investigated by researchers in such fields as industrial engineering and management science. Various algorithms have been proposed to solve such problems. However, the majority of these algorithms cannot be applied to a block transportation problem when a shipyard that uses a transporter, a large vehicle employed for moving weight, is considered. In this study, a hybrid optimisation algorithm is proposed for solving a block transportation problem when multiple transporters are used. With regards to the transporters, a minimisation of the travel distance without loading of and interference between the transporters is considered. A block transportation scheduling system is then developed based on the proposed algorithm. The developed system is applied to an actual block transportation scheduling problem of a shipyard. From the attained results, we demonstrate that the proposed algorithm has the ability to effectively solve the block transportation scheduling problems of a shipyard.     

Economic lot and supply scheduling problem: a time-varying lot sizes approach

We study the economic lot and supply scheduling problem (ELSSP) that arises in the distribution and manufacturing industries. The ELSSP involves the simultaneous scheduling of end-item production and inbound transportation of input materials over an infinite time horizon to minimise the average costs of inventory, production set-up and transportation. We present a new methodology based on a time-varying lot sizes approach for the ELSSP. We also provide computational experiments showing that the developed algorithm outperforms the existing heuristic for improved integrated scheduling.     

Models and optimisation approaches for scheduling steelmaking–refining–continuous casting production under variable electricity price

This paper studies the steelmaking–refining–continuous casting (SRCC) scheduling problem with considering variable electricity price (SRCCSPVEP). SRCC is one of the critical production processes for steel manufacturing and energy intensive. Combining the technical rules used in iron-steel production practice, time-dependent electricity price is considered to reduce the electricity cost and the associate production cost. A decomposition approach is proposed for the SRCCSPVEP. Without considering the electrical factor, the first phase applies the mathematical programming method to determine the relative schedule plan for each cast. In the second phase, we formulate a scheduling problem of all casts subject to resource constraint and time-dependent electricity price. A heuristic algorithm combined with the constraint propagation is developed to solve this scheduling problem. To investigate and measure the performance of the proposed approach, numerous instances are randomly generated according to the collective data from a well-known iron-steel plant in China. Computational results demonstrate that our algorithm is very efficient and effective in providing high-quality scheduling plans, and the electricity cost can be reduced for the iron-steel plant.     

Applied column generation-based approach to solve supply chain scheduling problems

More and more enterprises have chosen to adopt a made-to-order business model in order to satisfy diverse and rapidly changing customer demand. In such a business model, enterprises are devoted to reducing inventory levels in order to upgrade the competitiveness of the products. However, reductions in inventory levels and short lead times force the operation between production and distribution to cooperate closely, thus increasing the practicability of integrating the production and distribution stages. The complexity of supply chain scheduling problems (integrated production and distribution scheduling) is known to be NP-hard. To address the issues above, an efficient algorithm to solve the supply chain scheduling problem is needed. This paper studies a supply chain scheduling problem in which the production stage is modelled by an identical parallel machine scheduling problem and the distribution stage is modelled by a capacitated vehicle routing problem. Given a set of customer orders (jobs), the problem is to find a supply chain schedule such that the weighted summation of total job weighted completion time and total job delivering cost are minimised. The studied problem was first formulated as an integer programme and then solved by using column generation techniques in conjunction with a branch-and-bound approach to optimality. The results of the computational experiments indicate that the proposed approach can solve the test problems to optimality. Moreover, the average gap between the optimal solutions and the lower bounds is no more than 1.32% for these test problems.     

A decision-making approach for nesting scheduling: A textile case

In many industrial cases, the nesting problem and the scheduling problem have to be addressed at the same time. The complexity of the combined problem often prevents to take effectively into account both nesting efficiency and overall production objectives. This paper presents a scheduling approach for the combined problem of production scheduling and nesting. The aim of the proposed approach is to provide a good solution both for the nesting and scheduling problem. The approach involves the generation of scheduling alternatives, their transformation through a rule base mechanism into nesting solutions and finally their evaluation using different criteria that reflect the overall production objectives such as meeting due dates, minimizing of the cost and maximizing the machines and stock sheet utilisation. The proposed approach has been implemented in a software system for the purpose of solving a problem in the textile industry. Specifically, the scheduling of the carpet weaving processa problem of nesting rectangular patterns under complex production constraints-has been examined. A set of experiments has been conducted for producing realistic nesting schedules in order to evaluate the proposed system's performance. The results show that the proposed approach may be applied in real-life manufacturing processes under complex production constraints and multiple objectives.     

A decomposition-based approach to flexible flow shop scheduling under machine breakdown

Manufacturing systems in real-world production are generally dynamic and often subject to a wide range of uncertainties. Recently, research on production scheduling under uncertainty has attracted substantial attention. Although some methods have been developed to address this problem, scheduling under uncertainty remains inherently difficult to solve by any single approach. This article considers makespan optimisation of a flexible flow shop (FFS) scheduling problem under machine breakdown. It proposes a novel decomposition-based approach to decompose an FFS scheduling problem into several cluster scheduling problems which can be solved more easily by different approaches. A neighbouring K-means clustering algorithm is developed to first group the machines of an FFS into an appropriate number of machine clusters, based on a proposed machine allocation algorithm and weighted cluster validity indices. Two optimal back propagation networks, corresponding to the scenarios of simultaneous and non-simultaneous job arrivals, are then selectively adopted to assign either the shortest processing time (SPT) or the genetic algorithm (GA) to each machine cluster to solve cluster scheduling problems. If two neighbouring machine clusters are allocated with the same approach, they are subsequently merged. After machine grouping and approach assignment, an overall schedule is generated by integrating the solutions to the sub-problems. Computation results reveal that the proposed approach is superior to SPT and GA alone for FFS scheduling under machine breakdown.     

Production scheduling optimization algorithm for the hot rolling processes

The hot rolling production scheduling problem is an extremely difficult and time-consuming process, so it is quite difficult to achieve an optimal solution with traditional optimization methods owing to the high computational complexity. To ensure the feasibility of solutions and improve the efficiency of the scheduling, this paper proposes a vehicle routing problem (VRP) to model the problem and develops an easily implemented hybrid approach (QPSO-SA) to solve the problem. In the hybrid approach, quantum particle swarm optimization (QPSO) combines local search and global search to search the optimal results and simulated annealing (SA) employs certain probability to avoid getting into a local optimum. The computational results from actual production data have shown that the proposed model and algorithm are feasible and effective for the hot rolling scheduling problem.     

A multi-objective scatter search for the ladle scheduling problem

We consider the ladle scheduling problem, which can be regarded as a vehicle routing problem with semi-soft time windows and adjustment times. The problem concerns allocating ladles to serve molten steel based on a given steelmaking scheduling plan, and determining the modification operations for the empty ladles after the service process. In addition, combining the controllable processing time of molten steel, the other aspect of the problem is to determine the service start times taking into consideration the technological constraints imposed in practice. We present a non-linear mathematical programming model with the conflicting objectives of minimising the occupation ratio of the ladles and maximising the degree of satisfaction with meeting the soft windows. To solve the multi-objective model, we develop a new scatter search (SS) approach by re-designing the common components of SS and incorporating a diversification generator, a combination method and a diversification criterion to conduct a wide exploration of the search space. We analyse and compare the performance of the proposed approach with a multi-objective genetic algorithm and with manual scheduling adopted in practical production using three real-life instances from a well-known iron–steel production plant in China. The computational results demonstrate the effectiveness of the proposed SS approach for solving the ladle scheduling problem.     

The model of maintenance planning and production scheduling for maximising robustness

The accuracy of prediction and detection capability have a strong influence over the efficiency of the bottleneck, all equipment and the production system. The function of predictive scheduling is to obtain stable and robust schedules for a shop floor. The first objective is to present an innovative maintenance planning and production scheduling method. The approach consists of four modules: a database to collect information about failure-free times, a prediction module of failure-free times, predictive scheduling and rescheduling module, a module for evaluating the accuracy of prediction and maintenance performance. The second objective is to apply the proposed methods for a job shop scheduling problem. Usually, researchers who are concerned about maintenance scheduling do not take unexpected disturbances into account. They assume that machines are always available for processing tasks during the future-planned production time. Moreover, researches use the criteria that are not effective to deal with the situation of unpredicted failures. In this paper, a method based on probability theory is proposed for maintenance scheduling. For unpredicted failures, a rescheduling method is also proposed. The evaluation module which gives information about the degradation of each performance measure and the stability of a schedule is proposed.     

Advanced production scheduling for batch plants in process industries

An Advanced Planning System (APS) offers support at all planning levels along the supply chain while observing limited resources. We consider an APS for process industries (e.g. chemical and pharmaceutical industries) consisting of the modules network design (for long–term decisions), supply network planning (for medium–term decisions), and detailed production scheduling (for short–term decisions). For each module, we outline the decision problem, discuss the specifi cs of process industries, and review state–of–the–art solution approaches. For the module detailed production scheduling, a new solution approach is proposed in the case of batch production, which can solve much larger practical problems than the methods known thus far. The new approach decomposes detailed production scheduling for batch production into batching and batch scheduling. The batching problem converts the primary requirements for products into individual batches, where the work load is to be minimized. We formulate the batching problem as a nonlinear mixed–integer program and transform it into a linear mixed–binary program of moderate size, which can be solved by standard software. The batch scheduling problem allocates the batches to scarce resources such as processing units, workers, and intermediate storage facilities, where some regular objective function like the makespan is to be minimized. The batch scheduling problem is modelled as a resource–constrained project scheduling problem, which can be solved by an efficient truncated branch–and–bound algorithm developed recently. The performance of the new solution procedures for batching and batch scheduling is demonstrated by solving several instances of a case study from process industries.     

一类求解带随机成本的生产运输问题的线性逼近方法

生产和运输集成计划问题在许多工业工程领域都普遍存在。要给出最优的生产和运输计划就必须考虑实际工业管理过程中存在的不确定性因素。本文研究了生产厂家的生产能力、商家的需求量和单位运输成本等因素为随机变量情况下的产品生产与运输成本问题,建立了该类问题的随机优化模型。在一定的假设条件下,推导了所建模型的确定等价类。基于问题的结构特征,提出了求解生产和运输计划的一种线性逼近方法,数值例子表明该种方法的应用前景。     

遗传算法在水泥矿山卡车运输调度系统中的应用

根据露天矿山运输调度系统的复杂性与非线性特性，建立了实时运输调度系统模型；运用遗传进化算法中的选择、交叉、变异、插入、迁移算子的寻优迭代计算，成功地解决了在开采工艺、产量、质量等多因素约束条件下的实时运输调度优化问题。并将其用于韶峰水泥原料矿山的生产运输调度系统，既降低了矿山运输成本，又协调了开采工艺、质量、产量之间的关系，取得了较好的效果。同时为矿山企业信息化建设和其他物流企业提供了重要的参考价值。