考虑工序相关性的动态Job shop调度问题启发式算法

提出一类考虑工序相关性的、工件批量到达的动态Job shop 调度问题,在对工序相关性进行了定义和数学描述的基础上,进一步建立了动态Job shop 调度问题的优化模型。设计了一种组合式调度规则RAN(FCFS,ODD),并提出了基于规则的启发式算法以及该类动态Job shop 调度问题的算例生成方法。为验证算法和比较评估调度规则的性能,对算例采用文献提出的7种调度规则和RAN(FCFS,ODD)进行了仿真调度,对调度结果的分析表明了算法的有效性和RAN(FCFS,ODD)调度规则求解所提出的动态Job Shop 调度问题的优越性能。     

基于粒子群优化和模拟退火的混合调度算法

提出了一种离散粒子群调度算法，采用基于工序的编码方式及相应的位置和速度更新方法，使具有连续本质的粒子群算法直接适用于调度问题。针对粒子群算法容易陷入局部最优的缺陷，将其与模拟退火算法结合，得到了粒子群-模拟退火算法、改进的粒子群算法、粒子群-模拟退火交替算法以及粒子群-模拟退火协同算法等4种混合调度算法。仿真结果表明，混合算法均具有较高的求解质量。     

基于Petri网和混合算法的作业车间优化

采用赋时变迁Petri网,建立了一种作业车间调度模型.通过为机器分配工序来消解因机器库所共享而引起的冲突,得到了表示调度方案的标志图,给出了一种生成可行调度标志图的方法.同时,提出了一种变迁激发序列编码的离散版粒子群算法,并将模拟退火算法嵌入到该粒子群算法中,以提高算法的优化性能.仿真结果验证了混合算法的可行性和有效性.     

求解随机Job Shop调度问题的混合分布估计算法

提出一种混合分布估计算法用于求解具有随机工时的Job shop调度问题。建立随机Job shop调度问题(Stochastic Job shop scheduling problem, SJSSP)数学模型并给出随机期望值模型的评价方法。为提高种群多样性,将(μ+λ)-进化策略(Evolutionary strategy, ES)的重组、变异过程引入分布估计算法(Estimation of distribution algorithm, EDA),构造一种混合分布估计算法,ES-EDA。根据所采用的基于工序的编码方式,对父代工序继承率的概念进行了定义,并为重组过程设计基于父代工序继承率的个体重组方法,该方法不仅能使子代有效继承父代的优良特征,同时可避免非法解的产生。在标准算例FT06、FT10、FT20的基础上构造加工时间随机的3组算例,并选择文献中的5种算法作为混合分布估计算法的对比算法,仿真试验结果表明混合分布估计算法在优化性能方面具有明显优势。     

基于混合粒子群算法的汽车零件精冲车间调度研究

针对传统遗传算法在车间作业调度问题难以解决求解约束优化问题时存在难以同时兼顾求解质量和收敛效率这一问题,通过采用了基于工序编码的方式生成可行调度及借鉴遗传算法单点交叉方法,生成基于工件的交叉算子作为粒子的更新方式,将改进后的粒子群优化算法用于求解精冲零件车间调度问题,并在算法中通过利用局部搜索的方式提升粒子群中粒子收敛效率。通过对典型的调度测试问题进行模拟实验,证明了改进后的混合粒子群算法对于求解车间调度问题的适用性及具有不错的求解性能。     

基于粒子群优化和变邻域搜索的混合调度算法

提出了用于解决作业车间调度问题的离散版粒子群算法.该算法采用基于工序的编码和新的位置更新策略,使具有连续本质的粒子群算法直接适用于调度问题.同时,针对粒子群算法容易陷入局部最优的缺陷,利用粒子群算法和变邻域搜索算法的互补性能,设计了粒子群-变邻域搜索算法、改进的粒子群算法、粒子群-变邻域搜索交替算法和粒子群-变邻域搜索协同算法4种混合调度算法.仿真结果表明,混合算法能够有效地、高质量地解决作业车间调度问题.     

并行机调度问题粒子群优化研究

采用粒子群算法优化并行机调度问题,提出了基于机器和粒子位置取整的粒子编码方法和基于工件和粒子位置次序的粒子编码方法,并给出了两种不同粒子编码方法所对应的粒子群算法的步骤.通过对两个并行机算例的计算说明,基于两种不同编码方法的粒子群算法都能有效地对并行机调度问题进行优化,其中,基于工件和粒子位置次序的粒子编码所对应粒子群算法的优化性能要好些.     

基于混合粒子群算法具有交货期瓶颈的作业车间调度问题

为了解决一类具有交货期瓶颈的作业车间调度问题,给出了基于订单优势的交货期满意度和交货期瓶颈资源确定方法,以工件拖期加权和最小为优化目标,建立了基于交货期满意度和瓶颈资源约束的作业车间调度模型;为了求解该调度模型,设计了一种基于模拟退火的混合粒子群算法,该算法采用随机工序表达方式进行编码,并在模拟退火算法中引入变温度参数来提高算法效率。通过随机仿真,分别采用PSO-SA、SA和PSO对所建立的调度模型进行求解,结果显示PSO-SA算法的广泛性好、求解效率高且算法的稳定性好,验证了模型和算法的有效性。     

双资源约束的鲁棒Job Shop调度问题研究

针对机器-工人双资源约束下加工时间具有随机性的Job shop调度问题(Job shop scheduling problems,JSSP),考虑工人熟练程度差异和工人数量不足的约束,采用鲁棒调度的方法建立机器-工人双资源约束的鲁棒Job shop调度模型(Dual-resource constrained robust JSSP,DR-RJSSP).鉴于DR-RJSSP同时考虑工人合理指派和双目标优化,提出机器-工人两阶段指派方法,在主动降低加工时间随机扰动的同时最小化工人约束对调度性能的影响.其次,提出多目标混合分布估计算法求解DR-RJSSP,以得到兼顾调度性能和鲁棒性的Pareto解集.最后,采用8组仿真算例将所提出的兼顾工人熟练程度和负载均衡的指派策略与基于熟练程度的指派策略和随机指派策略进行对比,验证了所提指派策略的Pareto优化性能.此外,通过对制造企业调度案例的仿真分析,验证了基于两阶段指派策略的MO-HEDA求解DR-RJSSP的有效性.     

混合粒子群优化算法求解多车辆拖动货物问题

为确定码头卜集装箱运输到目标位置的顺序和运输的车辆,提出了多车辆拖动货物问题,该问题需要考虑空间约束对车辆调度过程的影响.针对该问题,建立了整数规划数学模型,证明了该问题为NP完全难题,提出了四种解的编码方式,并利用模拟退火算法与粒子群优化算法结合的混合粒子群优化算法进行求解.将计算结果与模拟退火算法、粒子群优化算法进行了比较,结果表明,使用混合粒子群优化算法并采用先到先服务规则的两部分编码方法计算得到的解最好.     

一种基于GA-SA-TS算法的车间调度方法的研究

运用现代优化算法来解决车间调度这类NP完全问题是现在普遍使用的方法。本文将模拟退火算法和禁忌搜索算法的思想与遗传算法相结合,改善了传统遗传算法中单一的交叉和变异机制,提出了模拟退火-交叉机制和禁忌搜索-变异机制,最终形成了一种适用于解决车间调度方面问题的GA-SA-TS混合遗传算法。三种算法取长补短,避免了遗传算法局部搜索能力差和易早熟的缺点。同时运用GA-SA-TS算法,针对实际车间调度问题进行了仿真。通过该仿真结果可以看出,GA-SA-TS混合遗传算法对于解决车间调度问题是可行的,且在解的质量方面有所提高。     

An effective hybrid particle swarm optimization for no-wait flow shop scheduling

The no-wait flow shop scheduling that requires jobs to be processed without interruption between consecutive machines is a typical NP-hard combinatorial optimization problem, and represents an important area in production scheduling. This paper proposes an effective hybrid algorithm based on particle swarm optimization (PSO) for no-wait flow shop scheduling with the criterion to minimize the maximum completion time (makespan). In the algorithm, a novel encoding scheme based on random key representation is developed, and an efficient population initialization, an effective local search based on the Nawaz-Enscore-Ham (NEH) heuristic, as well as a local search based on simulated annealing (SA) with an adaptive meta-Lamarckian learning strategy are proposed and incorporated into PSO. Simulation results based on well-known benchmarks and comparisons with some existing algorithms demonstrate the effectiveness of the proposed hybrid algorithm.     

A hybrid Nelder–Mead simplex and PSO approach on economic and economic-statistical designs of MEWMA control charts

Economic design of a control chart involves determining its basic parameters such that a cost function is minimized. This design when statistical performance measures are also considered is referred to as the economic-statistical design. In this paper, a simplex-based Nelder–Mead algorithm is used in combination with a particle swarm meta-heuristic procedure to solve both the economic and economic-statistical designs of a MEWMA control chart. The application results on extensive simulation experiments show that the particle swarm can lead the Nelder–Mead algorithm to better results. Furthermore, a comparative study is performed on the performances of three different algorithms of the Nelder–Mead, the particle swarm optimization (PSO), and the hybrid PSO and Nelder–Mead (PSO–NM). In this study, five different performance measures are taken into consideration and the results for both the economic and the economic-statistical models are reported at the end.     

Hybrid discrete particle swarm optimization for multi-objective flexible job-shop scheduling problem

Flexible job-shop problem has been widely addressed in literature. Due to its complexity, it is still under consideration for research. This paper addresses flexible job-shop scheduling problem (FJSP) with three objectives to be minimized simultaneously: makespan, maximal machine workload, and total workload. Due to the discrete nature of the FJSP problem, conventional particle swarm optimization (PSO) fails to address this problem and therefore, a variant of PSO for discrete problems is presented. A hybrid discrete particle swarm optimization (DPSO) and simulated annealing (SA) algorithm is proposed to identify an approximation of the Pareto front for FJSP. In the proposed hybrid algorithm, DPSO is significant for global search and SA is used for local search. Furthermore, Pareto ranking and crowding distance method are incorporated to identify the fitness of particles in the proposed algorithm. The displacement of particles is redefined and a new strategy is presented to retain all non-dominated solutions during iterations. In the presented algorithm, pbest of particles are used to store the fixed number of non-dominated solutions instead of using an external archive. Experiments are performed to identify the performance of the proposed algorithm compared to some famous algorithms in literature. Two benchmark sets are presented to study the efficiency of the proposed algorithm. Computational results indicate that the proposed algorithm is significant in terms of the number and quality of non-dominated solutions compared to other algorithms in the literature.     

Maximizing structure performances of a sandwich panel with hybrid composite skins using particle swarm optimization algorithm

A sandwich panel, composed of hybrid laminate skins of AL (aluminum)-CFRP-GFRP and aluminum honeycomb core, was optimized for maximizing the structural performance. Stacking sequence of the three different materials comprising the hybrid laminate skins and individual ply angles are taken as design variables in the present optimization problem. Synergizing a particle swarm optimization (PSO) algorithm method with a specially developed FEM program enables one to optimally decide the design variables and thereby significantly improve the sandwich performance. The present technique applying PSO to a hybrid sandwich in conjunction with FEA has extended the application area of optimization with a complex honeycomb sandwich that is not possible by the conventional method.     

An improved particle swarm optimization for the resource-constrained project scheduling problem

In this paper, an improved particle swarm optimization (PSO) algorithm is proposed for the resource-constrained project scheduling problem (RCPSP) which is widely applied in advanced manufacturing, production planning, and project management. The algorithm treats the solutions of RCPSP as particle swarms and employs a double justification skill and a move operator for the particles, in association with rank-priority-based representation, greedy random search, and serial scheduling scheme, to execute the intelligent updating process of the swarms to search for better solutions. The integration combines and overhauls the characteristics of both PSO and RCPSP, resulting in enhanced performance. The computational experiments are subsequently conducted to set the adequate parameters and compare the proposed algorithm with other approaches. The results suggest that the proposed PSO algorithm augments the performance by 9.26, 16.17, and 10.45 % for the J30, J60, and J120 instances against the best lower bound-based PSO currently available, respectively. Moreover, the proposed algorithms demonstrate obvious advantage over other proposals in exploring solutions for large-scale RCPSP problems such as the J60 and J120 instances.     

APPLYING PARTICLE SWARM OPTIMIZATION TO JOB-SHOPSCHEDULING PROBLEM

A new heuristic algorithm is proposed for the problem of finding the minimum makespan in the job-shop scheduling problem. The new algorithm is based on the principles of particle swarm optimization (PSO). PSO employs a collaborative population-based search, which is inspired by the social behavior of bird flocking. It combines local search (by self experience) and global search (by neighboring experience), possessing high search efficiency. Simulated annealing (SA) employs certain probability to avoid becoming trapped in a local optimum and the search process can be controlled by the cooling schedule. By reasonably combining these two different search algorithms, a general, fast and easily implemented hybrid optimization algorithm, named HPSO, is developed. The effectiveness and efficiency of the proposed PSO-based algorithm are demonstrated by applying it to some benchmark job-shop scheduling problems and comparing results with other algorithms in literature. Comparing results indicate that PSO-based a     

基于并行策略的改进混合粒子群算法及其应用

针对粒子群算法在解决高维度复杂优化易陷入局部最优的问题,构建差分进化算法(DE)、人工蜂群算法(ABC)与粒子群算法(PSO)并行运算的种群更新模型,提出基于并行策略的改进混合粒子群算法(DA_PSO)。以并行策略为基础,不改变种群规模,独立运行3种算法,每隔n次比较3种算法,获得当前最优点,并用其替换粒子群算法的种群最优点,利用PSO算法个体向种群最优靠近的特点,充分吸收DE算法、ABC算法的优点,使被替换后的PSO算法跳出局部最优,提升优化结果的质量。采用五种类型测试函数分别对ABC、DE、PSO和DA_PSO进行对比验证,结果表明:较其他算法而言,DA_PSO算法精度高,稳定性好,适应性强。同时为验证所提方法的科学性与实用性,将其应用在10t~32t/31.5m系列化的桥式起重机主梁金属结构轻量化设计中。     

A hybrid algorithm based on particle swarm optimization and simulated annealing for a periodic job shop scheduling problem

Generating schedules such that all operations are repeated every constant period of time is as important as generating schedules with minimum delays in all cases where a known discipline is desired or obligated by stakeholders. In this paper, a periodic job shop scheduling problem (PJSSP) based on the periodic event scheduling problem (PESP) is presented, which deviates from the cyclic scheduling. The PESP schedules a number of recurring events as such that each pair of event fulfills certain constraints during a given fixed time period. To solve such a hard PJSS problem, we propose a hybrid algorithm, namely PSO-SA, based on particle swarm optimization (PSO) and simulated annealing (SA) algorithms. To evaluate this proposed PSO-SA, we carry out some randomly constructed instances by which the related results are compared with the proposed SA and PSO algorithms as well as a branch-and-bound algorithm. In addition, we compare the results with a hybrid algorithm embedded with electromagnetic-like mechanism and SA. Moreover, three lower bounds (LBs) are studied, and the gap between the found LBs and the best found solutions are reported. The outcomes prove that the proposed hybrid algorithm is an efficient and effective tool to solve the PJSSP.