AGV调度优化：提升智能制造车间生产效率

版权申诉

5星 · 超过95%的资源 71 浏览量更新于2024-07-04 1 收藏 2.05MB PDF 举报

随着工业4.0和智能制造时代的到来，车间作业调度的问题变得日益重要，尤其是在物料搬运过程中。本文主要探讨了如何通过优化自动导引车(AGV)在制造车间中的应用来提升生产效率。车间作业调度的核心是找到一种方法，既能有效地安排作业流程，又能合理地规划AGV的路径，以达到最小化生产完成时间的目标。 AGV调度策略在这个背景下显得尤为关键。作者Shiyang Huang的研究针对的是一个复杂的问题，即带有AGV的车间作业调度，它将传统的车间作业问题转换为车辆调度问题，这涉及到了网络分配问题的确定性优化。作者提出了几种AGV调度策略，这些策略超越了传统的只考虑当前请求的分配规则，而是前瞻性地考虑了未来的运输需求，旨在提高资源的优化配置。通过与经典AGV分配规则进行比较，研究者进行了深入的案例分析，特别是在车间环境中的应用。结果显示，这种新型的AGV调度策略在显著减少作业等待时间以及优化其他与生产周期相关的指标上表现优越。这不仅有助于提升整体生产效率，还可能降低生产成本，增强整个制造系统的灵活性和响应能力。这篇论文不仅深化了我们对AGV在车间作业调度中的作用的理解，而且提供了实用的策略和方法，对于推进智能制造中物料搬运的高效管理具有重要意义。它为工业界和学术界提供了一个重要的参考框架，对于优化未来工业4.0环境下车间的运营模式具有深远影响。

also known to be NP-hard (Lenstra & Kan, 1981), and recent solution technique studies for VS/VR focus

on efficient heuristics such as evolutionary algorithm (Chiang & Lin, 2013) and simulation-based

approach (Villarreal, Garza-Reyes, & Kumar, 2016).

Optimization of JSSMH has mainly been studied for small size manufacturing shop floors, while recent

advancement of computational resources has reinvigorated the research in the JSSMH problem. Bilge and

Ulusoy (1995) formulated a nonlinear programming optimization model and proposed a heuristic time

window-based algorithm to solve the problem, and following this work, various models have been

proposed (Xie & Allen, 2015). Typically, JSSMH models aim to minimize production makespan, either

as a sole objective function or as a vital optimization criterion in the multi-objective settings. The essence

of JSSMH models consists of a set of job scheduling constraints that determines operations sequences on

machines, and a set of constraints that determines the routing of AGVs. Additional constraints may be

adopted considering shop floor conditions such as path constraints (Bürgy & Gröflin, 2016; Wang et al.,

2014) and task preemption (Dang & Nguyen, 2017; Izabela Nielsen, Dang, Nielsen, & Pawlewski, 2014).

Variations of JSSMH models include different presentation of vehicle movement (Ahmadi-Javid &

Hooshangi-Tabrizi, 2017), or adoption of different modeling methodologies such as constraint

programming (Novas & Henning, 2014) and Petri nets (Baruwa & Piera, 2016). The classic JSSMH

problem has been proved to be NP-hard (Na, Woo, & Lee, 2016).

The solution techniques to JSSMH in the body of literature are mainly heuristic based and specifically

genetic algorithms. When the JSSMH problem was firstly formulated, Bilge and Ulusoy (1995) derived a

time window of job pick-up at machines, which was used to regulate the movement of vehicles. Deroussi,

Gourgand, and Tchernev (2008) implemented three different metaheuristics algorithm including iterated

local search, simulated annealing, and a hybrid of these two to the JSSMH problem. Reddy and Rao

(2006) formulated the problem into a multi-objective model for scheduling both the vehicles and

machines, and the problem was solved with evolutionary algorithms. Abdelmaguid et al. (2004) proposed

a hybrid approach of heuristic and genetic algorithms that greedily search the vehicle starting operation to

solve the simultaneous vehicle and machine scheduling modules. Ahmadi-Javid and Hooshangi-Tabrizi

(2015) developed an algorithm with analogy to anarchic society, and the authors applied this algorithm to

JSSMH considering employee timetabling in a follow up study (Ahmadi-Javid & Hooshangi-Tabrizi,

2017). Zheng, Xiao, and Seo (2016) applied Tabu Search to the JSSMH problem. Baruwa and Piera

(2016) proposed a Petri-nets based model formulation for JSSMH and reported good performance. They

also reported detailed CPU time of the solution, which was lacking in the body of literature.

In this study, the model formulation for JSSMH problem is based on the model proposed by Bilge and

Ulusoy (1995). We applied a linearization to the formulation with conditional constraints to replace the

original nonlinear constraints so that the model can be solved with commercial solvers such as CPLEX,

and we added a constraint to start timing as soon as the first job is taken out of the Loading/Unloading

station (L/U). The results were used as a case study validation and for comparison. Optimization results

based on the proposed algorithm is compared to existing solution techniques in literature, and the

performance of the proposed model is justified by its high efficiency and good solution accuracy.

Besides, to explain the mechanism of the proposed algorithm, a new visualization method is adopted

based on traditional Gantt charts to present the job schedule and AGV movement simultaneously, and we

use it to explain how the proposed algorithm works with examples. The new visualization contains all the

information in traditional vehicle-implemented Gantt charts in which vehicles are treated as additional

machines; however, the routes and schedules of AGV fleet on the shop floor are explicitly presented.

Optimization results based on the proposed algorithm is compared to existing solution techniques in

literature, and the performance of the proposed model is justified by its high efficiency and good solution

accuracy.

1.2.3. JSSMH with Variable Processing Time

Limited attention has been paid to the production scheduling problems that job processing time is

variable, which has been reflected many production scenarios. As mentioned in some previous studies in

JSSMH, when human activity is involved in job processing, the job processing time can be affected by

variability of human manipulation, such as random redundant motion or slowing down due to tiredness

(Fink et al., 2014; Liu, Fan, Zhao, & Wang, 2017). Jobs themselves can have inherent variability in

processing time too. For example, metal products’ operation time can be influenced by a series of factors

(Yang, Chen, Wei, & Chen, 2018), as well as industrial chemical processes (Bonfill, Espuna, &

Puigjaner, 2005). There are two common types of variation reported in the body of literature, processing

time in random distribution and deteriorating processing time. However, variable processing time has not

been considered in job shop scheduling when material handling is part of decision making. With material

handling system as an integral part of production, it is essential to take this into consideration when

making production decisions.

Random processing time in production scheduling problems usually results from inaccurate data

collection or uncontrollable operations. Sakawa and Kubota (2000) applied genetic algorithms to fuzzy

programming for multi-objective job shop scheduling problems in which uncertain processing time and

due date were introduced, and in the case study each operation had three possible realized processing

times in triangular distribution. Bonfill, Espuna, & Puigjaner (2005) formulated a two-stage stochastic

programming model based on job shop scheduling for chemical processes where reaction time is

uniformed distributed. Such models were also described as Stochastic Job Shop Scheduling (SJSS)

problems, while the material handling was not included and it was often assumed that operations could

start immediately after completion of the previous operation. In reality, introducing material handling to

the optimized solution of SJSS will make the problem more realistic; however, also much more

complicated. Hence simulation has been commonly utilized when randomness exists in JSSMH (Xie &

Allen, 2015). With a large number of experiments, simulation could help in developing heuristic shop

floor management strategy (Wang et al., 2014). The strategy can also be flexible to implement operation

mechanisms, such as behavior rules (Ng, Eheart, Cai, & Braden, 2011; Y. Zhang, Huang, Sun, & Yang,

2014) and optimization-based decision making (Almeder, Preusser, & Hartl, 2009; Sacone & Siri, 2009).

Deterioration reflects the phenomenon that job processing becomes longer as the production process goes.

Deterioration was studied first by Gupta and Gupta (1988) in steel rolling mills. Following that, a variety

of researchers studied deterioration in job shop scheduling problems in various production scenarios, such

as single machine (Gawiejnowicz, Lee, Lin, & Wu, 2011), two-machine (W. C. Lee, Shiau, Chen, & Wu,

2010) and parallel machine based job shop scheduling (X. Huang, Wang, & Ji, 2014). Deterioration

brought additional difficulty to optimally scheduling the jobs hence some heuristic solution techniques

were also proposed (Kuo, Hsu, & Yang, 2012; Rustogi & Strusevich, 2012). In deteriorating job

processing scenario, the processing time is, to a large degree, dependent on starting time of the operation,

and researchers have reported multiple dependency relationships. The simplest case is that the processing

time is linear to the operation start time (W. C. Lee et al., 2010), but it also common that processing time

can be exponential to the processing sequence of jobs (X. Zhang, Wu, Lin, & Wu, 2018). In this study,

both dependency relationships are discussed with corresponding model formulation of JSSMH.

The major contribution of this research can be summarized as follows. Firstly, we introduce variable

processing time to the formulation of JSSMH. The model formulation has been derived to reflect real

production practice, including the production scenario with random and deteriorating processing time.

Secondly, we proposed the Stochastic Programming based JSSMH (SP-JSSMH) solution techniques to

find the expected shortest makespan when job processing times are random, and solved the SP-JSSMH

models with Pyomo. Thirdly, we propose a series of models for different dependency functions when

deterioration exists, and the models are solvable with CPLEX including the formulation with linear

dependency function and that with exponential dependency function but can be linearized by

reformulating the model.

1.3 Dissertation Structure

The remainder of the dissertation is organized as follows.

Chapter 2 presents a few proposed AGV dispatching strategies in which the shop floor can be planned

with a large number of jobs and potential uncertainties. The strategies are based on deterministic

optimization of assignment problems in network optimization, and with these strategies, AGVs are

assigned to work centers based on mathematical programming models minimizing the total waiting time

of jobs in a decision horizon in which the status of vehicles as well as jobs in work centers can be

predicted. The strategies are demonstrated in a case study based on a shop floor in literature and are

compared with classic AGV assignment rules including random assignment and nearest vehicle/shortest

travel time rule. The results show that hybrid strategies based on the proposed dispatching strategies and

classic assignment rules outperform pure classic strategy in minimizing jobs’ waiting time on the shop

floor.

Chapter 3 presents an efficient algorithm to solve deterministic JSSMH. The proposed algorithm starts

from an optimal solution under a large vehicle fleet, and iteratively reduces the number of available

vehicles until the fleet size is equal to the original requirements. In each iteration, one vehicle is removed

from the incumbent schedule, and remaining vehicles are reassigned to the transportation of operations

according to a set of specially designed heuristic rules, all while the schedule is simultaneously adjusted

due to vehicle reassignment. The algorithm stops when all operations are served and the AGV fleet size

meets the job shop requirements. A quadratic optimization model is formulated to initialize the vehicle

assignment. The algorithm is compared to existing solving methods in literature on optimized production

makespan and solution efficiency based on the same data sets, and the results suggest that the proposed

algorithm can achieve comparable solution quality on makespan with much higher efficiency.

Chapter 4 demonstrates the validity of considering variable processing time in optimization of JSSMH. A

two-stage stochastic programming model is formulated to account for randomly distributed processing

time, and two additional models are formulated for different deterioration scenarios. The models are

validated with small job set examples, and the optimized shop floor makespans with solutions of

proposed models are compared to the makespans with solutions of classic JSSMH excluding randomness

or deterioration of processing time in modeling. The proposed models prove to be superior in

performance with the realization of variable processing time.

剩余91页未读，继续阅读

码丽莲梦露

粉丝: 8369
资源: 16

AGV调度优化：提升智能制造车间生产效率

Timing Optimization Through Clock Skew Scheduling

Implementation of an Ant Colony Optimization technique for job shop scheduling problem

Invasive weed optimization algorithm for optimization no-idle flow shop scheduling problem

Optimization of a Segmented Filter with a New Error Diffusion Approach

Compiler Optimization on VLIW Instruction Scheduling for Low Power笔记

Optimization of Generation and Detection of WDM Signals with Advanced Modulation Formats

Privacy-Preserving Optimization of Cross-Domain Firewalls with Dynamic Rule Updates

Fuzzy linear model for production optimization of mining systems with multiple entities (2011年)

Multi-objective optimization of community detection using discrete teaching-learning-based optimization with decomposition

Enhanced Binary Particle Swarm Optimization (BPSO) with 6 new transfer functions:An Enhanced Binary Particle Swarm Optimization algorithm (VPSO) with 6 new transfer functions:An Enhanced binary Particle Swarm Optimization algorithm (VPSO) with v-shape tra

最新资源