Operational Decisions in AGV-Served Flowshop Loops: Fleet Sizing and Decomposition

This paper considers design and operational issues that arise in repetitive manufacturing systems served by automated guided vehicles (AGVs) in loop layouts with unidirectional material flow. Such systems are in widespread industrial use, and play an important role in modern manufacturing environments. The objective considered is the minimization of AGV fleet size, given the minimum steady state cycle time required to produce a minimal job set (or equivalently, given the maximum throughput rate). We also study whether the decomposition of a large AGV-served flowshop loop into several smaller loops improves productivity. The original loop and the decomposed design are compared with respect to the minimum cycle time needed for the repetitive manufacture of a minimal job set. When there are three or more machines in the loop, finding the optimal cycle time is an intractable problem. We therefore use the genetic algorithm developed in the companion paper [17], to identify whether the original or the decomposed design is more efficient. Our study suggests that many systems perform more productively as a result of decomposition. Finally, we discuss a joint sequencing issue that arises in decomposed systems with limited buffers between the loops, and analyze the tractability of all the relevant joint sequencing problems.     

Solving the AGV Problem via a Self-Organizing Neural Network

Automated Guided Vehicle (AGV)-based material handling systems (MHS) are used widely in Flexible Manufacturing Systems (FMS). The problem of AGV consists of the decisions and the operational control strategies of dispatching, routeing and scheduling of a set of AGVs under given system environments and operational objectives. One remaining challenge is to develop effective methods of AGV decisions for improved system productivity. This paper describes a prototype neural network approach for the AGV problem in an FMS environment. A group of neural network models are proposed to perform dispatching and routeing tasks for the AGV under conditions of single or multiple vehicles, and with or without time windows. The goal is to satisfy the transport requests in the shortest time and in a non-conflicting manner, subject to the global manufacturing objectives. Based on Kohonen's self-organizing feature maps, we have developed efficient algorithms for the AGVs decisions, and simulation results have been very encouraging.     

Survey of research in the design and control of automated guided vehicle systems

Automated guided vehicles (AGVs) are used for the internal and external transport of materials. Traditionally, AGVs were mostly used at manufacturing systems. Currently, AGVs are also used for repeating transportation tasks in other areas, such as warehouses, container terminals and external (underground) transportation systems. This paper discusses literature related to design and control issues of AGV systems at manufacturing, distribution, transshipment and transportation systems. It is concluded that most models can be applied for design problems at manufacturing centres. Some of these models and new models already proved to be successful in large AGV systems. In fact, new analytical and simulation models need to be developed for large AGV systems to overcome large computation times, NP-completeness, congestion, deadlocks and delays in the system and finite planning horizons. We specify more specific research perspectives in the design and control of AGV systems in distribution, transshipment and transportation systems.     

“货到人”拣选系统中电商订单分批优化研究

本文在电商行业迅速发展及人工智能日趋成熟的背景下,研究以自动导引车(AGV)为搬运工具的“货到人”拣选系统订单分批问题。首先以最小化AGV搬运货架次数为目标建立订单分批模型,然后提出了基于货架相似度的两阶段订单分批算法,在第一阶段分为新批次创建及订单加入批次两个步骤得到初始解;在第二阶段采用局部搜索改进初始解。在算法中构造订单选取货架规则,定义货架相似度函数并设计两种方法创建新批次,同时考虑周转箱数量限制求解订单分批方案。最后通过实验测试验证了模型和算法的有效性,分析了两种批次创建方法的适用性,并通过灵敏度分析给出了合理的周转箱数量配置建议。本研究可为采用“货到人”拣选系统的企业通过订单分批优化进一步提高AGV拣选效率提供理论依据和实践指导。     

模糊加工时间排序问题的性质

本文根据实际背景提出加工时间为三角形模糊数的排序问题,分析这个问题的性质,并就进一步研究提出几个思考。     

No-wait scheduling of position dependent jobs and adjustable processing intervals

In this paper, we consider a single machine no-wait scheduling model whereby job processing times are general functions of their position in the job sequence. We assume that the single machine must operate at a certain cycle, which can be determined by the scheduler. Furthermore, exactly one job has to be completed by the end of each cycle. Using different variations of the Linear Assignment Problem formulation, we develop polynomial time algorithms for minimizing the following objectives: makespan, total completion time, maximum earliness and total earliness.     

Determination of the number of automated guided vehicles required at a semi-automated container terminal

This paper describes the development of a minimum flow algorithm to determine the number of automated guided vehicles (AGVs) required at a semi-automated container terminal. At such a terminal the containers are transported by AGVs from the quay cranes to the automated stacking cranes and vice versa. A model and a strongly polynomial time algorithm are developed to solve the case in which containers are available for transport at known time instants.     

DCA for solving the scheduling of lifting vehicle in an automated port container terminal

The container was introduced as a universal carrier for various goods in the 1960s and soon became a standard worldwide transportation. The competitiveness of a container seaport is marked by different success factors, particularly the time in port for ships. Operational problems of container terminals is divided into several problems, such as assignment of vessels, loading/unloading and storage of the containers, quay cranes scheduling cite, planning yard cranes cite and assignment of storage containers cite. In this work, the study will focus on piloting yard trucks. Two different types of vehicles can be used, namely automated guided vehicles (AGVs) and lifting vehicles (LVs). An AGV receives a container from a quay crane and transports containers over fixed path. LVs are capable of lifting a container from the ground by itself. The model that we consider is formulated as a mixed integer programming problem, and the difficulty arises when the number of binary variables increases. There are a lot of algorithms designed for mixed integer programming problem such as Branch and Bound method, cutting plane algorithm, . . . By using an exact penalty technique we treat this problem as a DC program in the context of continuous optimization. Further, we combine the DCA with the classical Branch and Bound method for finding global solutions.     

基于AGV的智能仓库系统订单分批问题研究

研究了基于自动引导小车(AGV)的“货到人”智能仓库订单分批拣选问题, 在同时考虑工作人员拣选商品成本和AGV搬运货架成本的前提下, 建立了以总成本极小化为目标函数的订单分批问题整数规划模型。根据订单中包含的商品信息和商品所在的货架信息构建了描述订单之间关系的加权相似度指标, 分析了加权相似度与总拣选成本之间的正相关关系。基于订单之间的加权相似度设计了求解模型的贪婪算法。利用具体算例进行模拟计算, 分析了加权系数的变化对订单分批结果的影响, 以及加权系数λ的取值与工作人员拣取一件商品的成本c₁和AGV搬运一次货架的成本c₂之间的关系, 得到了贪婪算法中加权系数λ的确定方法。进一步分析了贪婪算法的计算时间和计算效果, 结果显示, 通过适当选取加权系数, 利用贪婪算法可以在短时间内得到订单分批问题的近似最优解;对于小规模算例, 贪婪算法在最坏情况下近似比不超过1.35。利用本文的模型和算法进行订单分批, 兼顾了工作人员拣取商品的成本和AGV搬运货架的成本, 可以有效提高订单拣选效率, 降低订单拣选总成本。     

考虑路径冲突的AGV配置与调度优化

合理调度有限的码头资源以满足船舶的装卸时间要求是自动化集装箱码头的重要目标之一。针对自动化集装箱码头自动导引车(automated guided vehicle,AGV)配置与调度问题,考虑船舶装卸时间要求和AGV运输过程中的路径冲突,提出分阶段调度策略。将船舶装卸作业分为卸船阶段、装卸同步阶段、装船阶段三个阶段,在每个阶段中,建立以最小化最大完工时间和最小化AGV空载和等待时间为双目标的调度优化模型,并设计基于NSGA-Ⅱ的启发式算法求解。根据本阶段的实际完工时间,从最优解集中选择下一阶段AGV的配置与调度方案。最后对比其他调度方案表明本文调度方案能够满足集装箱船的装卸时间要求,且提高了AGV的利用率,更符合码头实际作业要求。     

Optimal location of dwell points in a single loop AGV system with time restrictions on vehicle availability

Since the workload of a manufacturing system changes over time, the material handling equipment used in the facility will be idle at certain time intervals to avoid system overload. In this context, a relevant control problem in operating an automated guided vehicle (AGV) system is where to locate idle vehicles. These locations, called dwell points, establish the response times for AVG requests. In this article, a dynamic programming algorithm to solve idle vehicle positioning problems in unidirectional single loop systems is developed to minimize the maximum response time considering restrictions on vehicle time available to travel and load/unload requests. This polynomial time algorithm finds optimal dwell points when all requests from a given pick-up station are handled by a single AGV. The proposed algorithm is used to study the change in maximum response time as a function of the number of vehicles in the system.     

Exact solution procedures for the balanced unidirectional cyclic layout problem

In this paper, we consider the balanced unidirectional cyclic layout problem (BUCLP) arising in the determination of workstation locations around a closed loop conveyor system, in the allocation of cutting tools on the sites around a turret, in the positioning of stations around a unidirectional single loop AGV path. BUCLP is known to be NP-Complete. One important property of this problem is the balanced material flow assumption where the material flow is conserved at every workstation. We first develop a branch-and-bound procedure by using the special material flow property of the problem. Then, we propose a dynamic programming algorithm, which provides optimum solutions for instances with up to 20 workstations due to memory limitations. The branch and bound procedure can solve problems with up to 50 workstations.     

Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: the bottleneck lower bound

This paper studies minimizing the flow time of a cyclic schedule for repeated identical jobs, where one job is started/completed in each cycle, subject to the schedule achieving maximum throughput. We propose a branch and bound method for a single machine problem, and use this method to derive an improved lower bound for the multiple machine problem.     

Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times

This paper considers single-machine scheduling problems with job delivery times where the actual job processing time of a job is defined by a function dependent on its position in a schedule. We assume that the job delivery time is proportional to the job waiting time. We investigate the minimization problems of the sum of earliness, tardiness, and due-window-related cost, the total absolute differences in completion times, and the total absolute differences in waiting times on a single-machine setting. The polynomial time algorithms are proposed to optimally solve the above objective functions. We also investigate some special cases of the problem under study and show that they can be optimally solved by lower order algorithms.     

The development of modular-based design in considering technology complexity

Applying modularity in the designing of products has been extensively researched recently to reduce the delay of product development. This paper presents a methodology of modular-based design in the conceptual stage of systems to support concurrent engineering (CE). First, the functions (Fs) are classified into different types of modules according to the correlation in design by using fuzzy cluster identification. Second, the optimal module type is selected based on the considerations of the manufacture and assembly complexities of the system for progressive parallel design. Third, the design priority of Fs within a module is scheduled by measuring the information content of Fs. As a result, the traditional design process is arranged as a series-parallel action to reduce the design time of products. Finally, an automated guided vehicle (AGV) system is used as an example to describe this method.     

Hybrid evolutionary optimization of the operation of pipeless plants

Pipeless plants are a new production concept in chemical engineering in which automated guided vehicles (AGVs) transport the substances in mobile vessels between processing stations. In the operation of such plants, decisions have to be made on the scheduling of the production, the assignment of the equipment and the routing of the AGVs that carry the vessels. The large number of interacting degrees of freedom prohibit the use of exact mathematical algorithms to compute optimal schedules. This paper describes the combination of an evolutionary scheduling algorithm with a simulation based schedule builder. The algorithm is tested on a real-life example and on a benchmark problem from the literature and yields considerably shorter makespans than a heuristic solution.     

订单带多工类工件时的极小迟后范围问题

本文考虑下述由多工类工件组成的订单的单机排序问题：每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类．当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间si．每一订单有一给定的应交工时间,订单的完工时间定义为该定单所含全部工件完工时的时间．我们希望适当排列这n个工件,使得订单的迟后范围最小．相应这一排序问题,文中依不同的背景给出了以下二种模式：同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,用GT,Ba来表示；同类工件一起连续加工,工件的完工时间为其本身的完工时间,用GT,Ja来表示．对于这两种模式的排序同题,我们均证明了其NP-hard性并给出了对应的分枝定界算法．     

Production scheduling with supply and delivery considerations to minimize the makespan

In this paper we study a scheduling model that simultaneously considers production scheduling, material supply, and product delivery. One vehicle with limited loading capacity transports unprocessed jobs from the supplier’s warehouse to the factory in a fixed travelling time. Another capacitated vehicle travels between the factory and the customer to deliver finished jobs to the customer. The objective is to minimize the arrival time of the last delivered job to the customer. We show that the problem is NP-hard in the strong sense, and propose an O(n) time heuristic with a tight performance bound of 2. We identify some polynomially solvable cases of the problem, and develop heuristics with better performance bounds for some special cases of the problem. Computational results show that all the heuristics are effective in producing optimal or near-optimal solutions quickly.     

A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time.     

Scheduling jobs with position-dependent processing times

The paper is devoted to some single machine scheduling problems, where job processing times are defined by functions dependent on their positions in the sequence. It is assumed that each job is available for processing at its ready time. We prove some properties of the special cases of the problems for the following optimization criteria: makespan, total completion time and total weighted completion time. We prove strong NP-hardness of the makespan minimization problem for two different models of job processing time. The reductions are done from the well-known 3-Partition Problem. In order to solve the makespan minimization problems, we suggest the Earliest Ready Date algorithms, for which the worst-case ratios are calculated. We also prove that the makespan minimization problem with job ready times is equivalent to the maximum lateness minimization problem.