A new model of scheduling in manufacturing: tasks, roles, and monitoring

For over 3 decades there was a belief that computer-based solutions would "solve" complex industrial scheduling problems, yet most manufacturing organizations still require human contributions for effective scheduling performance. We present a new model of scheduling for the development and implementation of effective scheduling systems within manufacturing companies. The model derives from investigating the work of 7 schedulers in 4 manufacturing environments using a qualitative field study approach, for which novel field-based data collection and analysis methods were developed. The results show that scheduling in practice comprises task, role, and monitoring activities and that the business environment influences a scheduler at work. A new definition of scheduling is presented that includes the significant facilitation and implementation aspects of human scheduling ignored by many computer-based scheduling approaches. The implications for this model extend across the domains of human factors and operations management, especially for the analysis and improvement of existing and new production planning and control processes and enterprise information systems. Actual or potential applications of this research include the analysis, design, and management of planning, scheduling, and control processes in industry; the selection, training, and support of production schedulers; and the allocation of tasks to humans and computer systems in industrial planning, scheduling, and control processes.     

An active learning genetic algorithm for integrated process planning and scheduling

In traditional approaches, process planning and scheduling are carried out sequentially, where scheduling is done separately after the process plan has been generated. However, the functions of these two systems are usually complementary. The traditional approach has become an obstacle to improve the productivity and responsiveness of the manufacturing system. If the two systems can be integrated more tightly, greater performance and higher productivity of a manufacturing system can be achieved. Therefore, the research on the integrated process planning and scheduling (IPPS) problem is necessary. In this paper, a new active learning genetic algorithm based method has been developed to facilitate the integration and optimization of these two systems. Experimental studies have been used to test the approach, and the comparisons have been made between this approach and some previous approaches to indicate the adaptability and superiority of the proposed approach. The experimental results show that the proposed approach is a promising and very effective method on the research of the IPPS problem.     

A constraint programming approach to tool allocation and production scheduling in flexible manufacturing systems

This paper presents a constraint programming (CP) methodology to deal with the scheduling of flexible manufacturing systems (FMSs). The proposed approach, which consists of both a model and a search strategy, handles several features found in industrial environments, such as limitations on number of tools in the system, lifetime of tools, as well as tool magazine capacity of machines. In addition, it tackles the problem in a integrated way by considering tool planning and allocation, machine assignment, part routing, and task timing decisions altogether in the approach. The formulation, which is able to take into account a variety of objective functions, has been successfully applied to the solution of test problems of various sizes and degrees of difficulty.     

基于Petri网和人工势场的柔性制造启发式优化方法

制造系统优化调度是NP难组合优化问题,而自动导引车(AGV)路径规划与任务分配紧密耦合,又极大加剧了问题的复杂性.基于此,提出一种基于Petri网和人工势场的启发式优化方法.首先,将制造系统的工艺工序描述为一个任务Petri网,将AGV系统描述为一个路径Petri网,将两个网合成在一起;然后,利用Petri网的拓扑结构,为网络结点设计势能参数,从而为Petri网赋予一个人工势场;接着,利用人工势场设计制造系统加工时间的启发式函数,并构建Petri网人工势场启发式A*算法,其中包括最大势差启发式函数和总体势差启发式函数,并验证最大势差启发式函数是可采纳的;最后,进行两组数值实验,实验结果表明,最大势差A*算法能够得到最优解,且平均计算效率比Dijkstra算法提高57%,但是无法满足大任务量的调度需求,而总体势差A*算法比最大势差A*算法平均计算效率提高至少1个数量级,能够在有限时间内求解AGV任务分配和路径规划的联合问题.     

Operations planning and scheduling problems in an FMS: An integrated approach

Operations planning and scheduling (OPS) problems in advanced manufacturing systems, such as flexible manufacturing systems, are composed of a set of interrelated problems, such as part-type batching, machine grouping, tool loading, routing, part input sequencing and on-line scheduling. In this paper, an integrated, simulation-based approach to the OPS problems is discussed. A detailed simulation model is developed using FORTRAN and SLAM II which integrates loading, part inputting, routeing and dispatching issues of the OPS. An experimental frame is developed which provides statistical analysis of the simulation output by developing an experimental design. Statistical analyses concerning a number of system parameters (e.g. loading strategies and scheduling rules) are performed on a set of performance measures.     

An optimization approach for the lot sizing and scheduling problem in the brewery industry

This study considers a production lot sizing and scheduling problem in the brewery industry. The underlying manufacturing process can be basically divided into two main production stages: preparing the liquids including fermentation and maturation inside the fermentation tanks; and bottling the liquids on the filling lines, making products of different liquids and sizes. This problem differs from other problems in beverage industries due to the relatively long lead times required for the fermentation and maturation processes and because the “ready” liquid can remain in the tanks for some time before being bottled. The main planning challenge is to synchronize the two stages (considering the possibility of a “ready” liquid staying in the tank until bottling), as the production bottlenecks may alternate between these stages during the planning horizon. This study presents a novel mixed integer programming model that represents the problem appropriately and integrates both stages. In order to solve real-world problem instances, MIP-based heuristics are developed, which explore the model structure. The results show that the model is able to comprise the problem requirements and the heuristics produce relatively good-quality solutions.     

A Petri net-based methodology to increase flexibility in service-oriented holonic manufacturing systems

Distributed control systems such as the holonic manufacturing systems and service-oriented architectures have demonstrated to provide higher levels of flexibility, notably in the planning and scheduling functionalities, if well exploited. In scheduling, the use of fixed process plans generated by traditional planning approaches, usually leads to unrealistic schedules due to the lack of considerations of the workshop status. IPPS approaches try to break the gap between these two functionalities in favor of providing flexible plans adapting to the shop floor's state. A key element in the creation of flexible process plans is the definition of a process model capable of representing alternatives solutions to the sequencing problem and therefore increasing the potential solution space. This paper presents a methodology to increase planning flexibility in service-oriented manufacturing systems (SOHMS). The methodology introduces a Petri net service-oriented process model (SOP model) capable of computing a product's deadlock free sequential space and adapts to the fractal character of holonic architectures. A set of modeling rules, with illustrations, is presented for the automatic generation of the Petri net, based on a set of precedence conditions. To explore the solution space represented by the SOP model a holonic interaction protocol is presented. Moreover, a set of behavioral strategies is proposed in order to cope with the effects of a possible combinatorial explosion. A study case applied workshop example is presented to illustrate the modeling process of SOP models, compute the sequential solution space and demonstrate how this notably increases the number of potentially goods feasible solutions.     

A modeling technique for loading and scheduling problems in FMS

In recent years, due to highly competitive market conditions, it has become necessary for manufacturing systems to have quick response times and high flexibility. Flexible manufacturing systems (FMS's) have gained attention in response to this challenge. FMS has the ability to produce a variety of parts using the same system. However this flexibility comes at the price, which is the development of efficient and effective methods for integrated production planning, and control.In this paper, we analyze the production planning problem in flexible manufacturing systems. We address the problems of part loading, tool loading, and part scheduling. We assume that there is a set of tools with known life and a set of machines that can produce a variety of parts. A batch of various part types is routed through this system with the assumption that the processing time and cost vary with the assignment of parts to different machines and assignment of various tool sets to machines. We developed a mathematical model to select machines and assign operations and the required tools to machines in order to minimize the summation of maximum completion time, material handling time, and total processing time.We first integrate and formulate loading, and routing, two of the most important FMS planning problems, as a 0–1 mixed integer programming problem. We then take the output from the integrated planning model and generate a detailed operations schedule. The results reported in this paper demonstrate the model efficiency and examine the performance of the system with respect to measures such as production rate and utilization.     

Neural networks for process scheduling in real-time communicationsystems

This paper presents the use of Hopfield-type neural networks for process scheduling in the area of factory automation, where bus-based communication systems, called FieldBuses, are widely used to connect sensors and actuators to the control systems. We show how it overcomes the problem of the computational complexity of the algorithmic solution. The neural model proposed allows several processes to be scheduled simultaneously; the time required is polynomial with respect to the number of processes being scheduled. This feature allows real-time process scheduling and makes it possible for the scheduling table to adapt to changes in process control features. The paper presents the neural model for process scheduling and assesses its computational complexity, pointing out the drastic reduction in the time needed to generate a schedule as compared with the algorithmic scheduling solution. Finally, the authors propose an on-line scheduling strategy based on the neural model which can achieve real-time adaptation of the scheduling table to changes in the manufacturing environment.     

Capacitated lot sizing and sequence dependent setup scheduling: an iterative approach for integration

We consider here the lot sizing and scheduling problem in single-level manufacturing systems. The shop floor is composed of unrelated parallel machines with sequence dependent setup times. We propose an integer programming model embedding precise capacity information due to scheduling constraints in a classical lot-sizing model. We also propose an iterative approach to generate a production plan taking into account scheduling constraints due to changeover setup times. The procedure executes two decision modules per iteration: a lot-sizing module and a scheduling module. The capacitated lot-sizing problem is solved to optimality considering estimated data and aggregate information, and the scheduling problem is solved by a GRASP heuristic. In the proposed scheme the information flow connecting the two levels is managed in each iteration. We report a set of computational experiments and discuss future work.     

Scheduling concurrent production over a finite planning horizon: polynomially solvable cases

The paper analyzes a manufacturing system made up of one workstation which is able to produce concurrently a number of product types with controllable production rates in response to time-dependent product demands. Given a finite planning horizon, the objective is to minimize production cost, which is incurred when the workstation is not idle and inventory and backlog costs, which are incurred when the meeting of demand results in inventory surpluses and shortages. With the aid of the maximum principle, optimal production regimes are derived and continuous-time scheduling is reduced to a combinatorial problem of sequencing and timing the regimes. The problem is proved to be polynomially solvable if demand does not exceed the capacity of the workstation or it is steadily pressing and the costs are “agreeable”.

Scope and purpose

Efficient utilization of modern flexible manufacturing systems is heavily dependent on proper scheduling of products throughout the available facilities. Scheduling of a workstation which produces concurrently a number of product types with controllable production rates in response to continuous, time-dependent demand is under consideration. Similar to the systems considered by many authors in recent years, a buffer with unlimited capacity is placed after the workstation for each product type. The objective is to minimize inventory storage, backlog and production costs over a finite planning horizon. Numerical approaches are commonly used to approximate the optimal solution for similar problems. The key contribution of this work is that the continuous-time scheduling problem is reduced to a combinatorial problem, exactly solvable in polynomial time if demand does not exceed the capacity of the workstation or the manufacturing system is organized such that the early production and storage of a product to reduce later backlogs are justified.     

Multicycle Polling Scheduling Algorithms for FieldBus Networks

The paper deals with the scheduling of periodic information flow in a FieldBus environment. The scheduling problem is defined from an analytical point of view, giving a brief survey of the most well-known solutions. One of these is called multicycle polling scheduling, which is based on the hypothesis that all the production periods of the periodic processes to be scheduled are harmonic. Although in some process control or manufacturing scenarios, this hypothesis may be acceptable, there are many real industrial processes to which it cannot be applied. The aim of the paper is to make a contribution towards solving the scheduling problem. It essentially concerns extension of the theory on which multicycle polling scheduling is based to a much more realistic and general scenario, where the periods of all the processes to be scheduled have arbitrary values. The authors present a new formulation of multicycle polling scheduling, called extended multicycle polling scheduling, and demonstrate that it comprises the scenario currently considered in the literature. Two algorithmic solutions for extended multicycle polling scheduling are then proposed, giving a computational complexity analysis which will highlight the capability of the algorithmic scheduling solutions to be performed on-line. The paper concludes by comparing the multicycle polling scheduling approach known in literature and the one presented in the paper. Comparison is performed by evaluating the use of available bandwidth to serve both periodic and asynchronous traffic in the two approaches.     

Applications of particle swarm optimisation in integrated process planning and scheduling

Integration of process planning and scheduling (IPPS) is an important research issue to achieve manufacturing planning optimisation. In both process planning and scheduling, vast search spaces and complex technical constraints are significant barriers to the effectiveness of the processes. In this paper, the IPPS problem has been developed as a combinatorial optimisation model, and a modern evolutionary algorithm, i.e., the particle swarm optimisation (PSO) algorithm, has been modified and applied to solve it effectively. Initial solutions are formed and encoded into particles of the PSO algorithm. The particles “fly” intelligently in the search space to achieve the best sequence according to the optimisation strategies of the PSO algorithm. Meanwhile, to explore the search space comprehensively and to avoid being trapped into local optima, several new operators have been developed to improve the particles’ movements to form a modified PSO algorithm. Case studies have been conducted to verify the performance and efficiency of the modified PSO algorithm. A comparison has been made between the result of the modified PSO algorithm and the previous results generated by the genetic algorithm (GA) and the simulated annealing (SA) algorithm, respectively, and the different characteristics of the three algorithms are indicated. Case studies show that the developed PSO can generate satisfactory results in both applications.     

Pricing and production lot-size/scheduling with finite capacity for a deteriorating item over a finite horizon

Although the lately evolved manufacturing technologies such as enterprise resource planning (ERP) provide a unified platform for managing and integrating core business processes within a firm, the decision-making between marketing and production planning still remains rather disjoint. It is due in large parts to the inherent weaknesses of ERP such as the fixed and static parameter settings and uncapacitated assumption. To rectify these drawbacks, we propose a decision model that solves optimally the production lot-size/scheduling problem taking into account the dynamic aspects of customer's demand as well as the restriction of finite capacity in a plant. More specifically, we consider a single product that is subject to continuous decay, faces a price-dependent and time-varying demand, and time-varying deteriorating rate, production rate, and variable production cost, with the objective of maximizing the profit stream over multi-period planning horizon. We propose both coordinated and decentralized decision-making policies that drive the solution of the multivariate maximization problem. Both policies are formulated as dynamic programming models and solved by numerical search techniques. In our numerical experiments, the solution procedure is demonstrated, comparative study is conducted, and sensitivity analysis is carried out with respect to major parameters. The numerical result shows that the solution generated by the coordinated policy outperforms that by the decentralized policy in maximizing net profit and many other quantifiable measures such as minimizing inventory investment and storage capacity.Scope and purposeWe consider a manufacturing firm who produces and sells a single product that is subjected to continuous decay over a lifetime, faces a price-dependent and time-varying demand function, shortages are allowed and a completely backlogged, and has the objective of determining price and production lot-size/scheduling so as to maximize the total profit stream over multi-period planning horizon. We develop a tactical-level decision model that solves the production scheduling problem taking into account the dynamic nature of customer's demand which is partially controllable through pricing schemes. As analogous to the sales and operations planning, the proposed scheme can be used as a coordination center of the APS system within a generic enterprise resource planning framework which integrates and coordinates distinct functions within a firm.This paper differs from the existing works in several ways. First, we propose a dynamic version of the joint pricing and lot-size/scheduling problem taking into account the capacitated constraint. Second, several key factors being considered in the model, such as the demand rate, deteriorating rate, production rate, and variable production cost are assumed time-varying that reflect the dynamic nature of the market and the learning effect of the production system. A third difference between the past research and ours is that the price can be adjusted upward or downward in our model, making the proposed pricing policy more responsive to the structural change in demand or supply.     

Distributed joint dynamic maintenance and production scheduling in manufacturing systems: Framework based on model predictive control and Benders decomposition

Scheduling the maintenance based on the condition, respectively the degradation level of the system leads to improved system's reliability while minimizing the maintenance cost. Since the degradation level changes dynamically during the system's operation, we face a dynamic maintenance scheduling problem. In this paper, we address the dynamic maintenance scheduling of manufacturing systems based on their degradation level. The manufacturing system consists of several units with a defined capacity and an individual dynamic degradation model, seeking to optimize their reward. The units sell their production capacity, while maintaining the systems based on the degradation state to prevent failures. The manufacturing units are jointly responsible for fulfilling the demand of the system. This induces a coupling constraint among the agents. Hence, we face a large-scale mixed-integer dynamic maintenance scheduling problem. In order to handle the dynamic model of the system and large-scale optimization, we propose a distributed algorithm using model predictive control (MPC) and Benders decomposition method. In the proposed algorithm, first, the master problem obtains the maintenance scheduling for all the agents, and then based on this data, the agents obtain their optimal production using the distributed MPC method which employs the dual decomposition approach to tackle the coupling constraints among the agents. The effectiveness of the proposed method is investigated on two case studies.     

多任务电镀线预测调度模型及应用

计算机控制的行车调度系统广泛地应用于先进制造系统中的材料搬运,电镀行车的调度方式,已经成为提高生产率的瓶颈问题。行车调度问题不同于古典的排序问题,已被证明为NP难题,迄今尚无法用数学模型直接求解。为了解决实际应用问题,本文提出了基于预测模型,采用在线滚动优化的调度方法。该方法提前计算出行车到达各个工位的具体时刻,并和行车实际到达各工位的时刻相比较,通过预测值和实际值的偏差,在允许范围内动态调整各工位的加工时间,以期兼顾产品质量和企业生产效率。通过生产线运用证明,在多批次小批量的生产过程中,采用该调度方法能提高生产效率近20%。实例表明,该调度方法是有效的。     

Mathematical model and discrete artificial Bee Colony algorithm for distributed integrated process planning and scheduling

With the development of the globalization of economy and manufacturing industry, distributed manufacturing mode has become a hot topic in current production research. In the context of distributed manufacturing, one job has different process routes in different workshops because of heterogeneous manufacturing resources and manufacturing environments in each factory. Considering the heterogeneous process planning problems and shop scheduling problems simultaneously can take advantage of the characteristics of distributed factories to finish the processing task well. Thus, a novel network-based mixed-integer linear programming (MILP) model is established for distributed integrated process planning and scheduling problem (DIPPS). The paper designs a new encoding method based on the process network and its OR-nodes, and then proposes a discrete artificial bee colony algorithm (DABC) to solve the DIPPS problem. The proposed DABC can guarantee the feasibility of individuals via specially-designed mapping and switching operations, so that the process precedence constraints contained by the network graph can be satisfied in the entire procedure of the DABC algorithm. Finally, the proposed MILP model is verified and the proposed DABC is tested through some open benchmarks. By comparing with other powerful reported algorithms and obtaining new better solutions, the experiment results prove the effectiveness of the proposed model and DABC algorithm successfully.     

An agent-based approach for e-manufacturing and supply chain integration

A major problem facing manufacturing organisations is how to provide efficient and cost-effective responses to the unpredictable changes taking place in a global market. This problem is made difficult by the complexity of supply chain networks coupled with the complexity of individual manufacturing systems within supply chains. Current systems such as manufacturing execution systems (MES), supply chain management (SCM) systems and enterprise resource planning (ERP) systems do not provide adequate facilities for addressing this problem. This paper presents an approach that would enable manufacturing organisations to dynamically and cost-effectively integrate, optimise, configure, simulate, restructure and control not only their own manufacturing systems but also their supply networks, in a co-ordinated manner to cope with the dynamic changes occurring in a global market. This is realised by a synergy of two emerging manufacturing concepts: Agent-based agile manufacturing systems and e-manufacturing. The concept is to represent a complex manufacturing system and its supply network with an agent-based modelling and simulation architecture and to dynamically generate alternative scenarios with respect to planning, scheduling, configuration and restructure of both the manufacturing system and its supply network based on the coordinated interactions amongst agents.     

Mathematical modeling and evolutionary algorithm-based approach for integrated process planning and scheduling

Traditionally, process planning and scheduling were performed sequentially, where scheduling was implemented after process plans had been generated. Considering their complementarity, it is necessary to integrate these two functions more tightly to improve the performance of a manufacturing system greatly. In this paper, a mathematical model of integrated process planning and scheduling has been formulated. And, an evolutionary algorithm-based approach has been developed to facilitate the integration and optimization of these two functions. To improve the optimized performance of the approach, efficient genetic representation and operator schemes have been developed. To verify the feasibility and performance of the proposed approach, experimental studies have been conducted and comparisons have been made between this approach and some previous works. The experimental results show that the integrated process planning and scheduling is necessary and the proposed approach has achieved significant improvement.     

An integrated agent-based approach for responsive control of manufacturing resources

Due to the dynamic fluctuation of customer demands in the global market, manufacturing enterprises are facing difficulties in rapidly responding to market changes. The aim of this research is to develop a system to integrate dynamic process planning and dynamic production scheduling for the purpose of increasing the responsiveness of adaptive manufacturing systems in accommodating dynamic market changes (rapidly changing demand patterns or product varieties). The concept of Multi-Agent Systems (MAS) has been adopted in this study. All of the tasks related to process planning, optimization and scheduling in this system are carried out by autonomous agents that are capable of interacting and negotiating with each other to bid for jobs and make decisions. On the one hand, this system optimizes the utilization of manufacturing resources and on the other hand, it also provides a platform where the reconfiguration of manufacturing systems can be assessed. This system has been implemented on a Java platform and a case study is provided to elaborate on this system and evaluate its implementation.