协同进化量子微分算法解决Flowshop调度问题

47 浏览量更新于2024-08-26 收藏 231KB PDF 举报

“一种新颖的协同进化量子微分算法，用于解决带有制造跨度最小化的阻塞流水车间调度问题” 在优化领域，流水车间调度问题（Flowshop Scheduling Problem, FSP）是一个经典且复杂的问题，其目标通常是最小化所有任务完成时间的最大值，即制造跨度（Makespan）。针对这一问题，研究者提出了一种创新的协同进化量子微分算法（Co-evolutionary Quantum Differential Algorithm, CQDA），专门用于解决阻塞流水车间调度问题（Blocking Flowshop Scheduling Problem, BFSP）。 CQDA结合了量子进化算法（Quantum-inspired Evolutionary Algorithm, QEA）和差分进化（Differential Evolution, DE）的优势。在算法设计中，引入了一种新型的量子旋转门机制，该机制能够有效地控制群体的进化趋势，同时增加种群的多样性，以避免早熟收敛和局部最优。此外，还开发了一种有效的QEA-变邻域搜索（Variable Neighborhood Search, VNS）协同进化策略，用于优化和提升当前最佳解的质量。实际实验中，CQDA在Taillard的标准测试实例上与几种相关的算法进行了对比，结果显示，CQDA的表现优于高效的启发式算法NEHLS，并且在平均相对百分比偏差（Average Relative Percentage Deviation, ARPD）上降低了约7%的最优解生成。这表明，CQDA在解决BFSP时具有更高的效率和解决方案质量。关键词：阻塞流水车间调度问题，协同进化，量子微分算法，制造跨度最小化，量子旋转门，差分进化，变邻域搜索这种新颖的CQDA算法不仅展示了量子计算和传统优化方法的融合潜力，也为解决实际工业生产中的调度问题提供了新的思路。通过改进的量子旋转门和协同进化策略，CQDA能够更有效地探索解决方案空间，从而提高找到全局最优解的可能性。未来的研究可能进一步优化这些策略，或者将其应用到其他复杂的调度问题中，以推动优化技术的发展。

A novel co-evolutionary quantum differential algorithm for blocking flowshop

scheduling problem with makespan minimization *

MA Pingkang, Sun Daoqing**, Yi Jingwei, WANG Hongtao

School of Mathematics and Computer Science, Anhui Normal University,

Wuhu, Anhui 241003, China

Email: sundq1966@163.com

Abstract—A novel Co-evolutionary Quantum Differential

Algorithm (CQDA) is proposed for the Blocking Flowshop

Scheduling Problem (BFSP) to minimize the makespan. The

CQDA combines Quantum-inspired Evolutionary Algorithm

(QEA) with Differential Evolutionary (DE). A novel quantum

rotating gate is designed to control the evolutionary trend and

increase the diversity of population. An effective QEA-VNS co-

evolutionary strategy is also developed to optimize and

improve the current best solution. Compared with several

related algorithms by actual experiments on the Taillard’s

benchmark instances, the results show that the performance of

CQDA is superior to the efficient heuristic algorithm NEH

and it drops down about 7% generated optimal solutions to the

Average Relative Percentage Deviation(ARPD).

Keywords- blocking flowshop scheduling; Quantum-inspired

Evolutionary Algorithm (QEA); Differential Evolutionary (DE);

co-evolutionary; makespan

I. INTRODUCTION

Flowshop Scheduling Problem (FSP) is a classical

combinational optimization problem, which applied widely

in many different industrial environments, such as

metallurgical, chemical, pharmaceuticals, textile, etc. The

problem is described as: a set N of n unrelated jobs is to be

processed on a set M of m machines. These machines are

disposed in series and each job needs to visit all of them in

the same order. This order can be assumed, without loss of

generality, to be 1… m. Therefore, each job j, j

∈

N is

composed of m tasks. The all machine processing times of

jobs are known in advance, non-negative and deterministic.

They are denoted by P

j,i

, j

∈

N, i

∈

M. The objective is to

obtain a production sequence of the n jobs on the m

machines so that a giver criterion is optimized. The

Blocking Flowshop Scheduling Problem (BFSP) is a further

constraint than the FSP. In the BFSP, because of the lack of

intermediate buffer storage between consecutive machines,

a job has to remain in the current machine until the next

machine is available, even if it has completed the process in

this machine. This increases the waiting time or productive

cycle and thus influences the production efficiency [1]. For

the computational complexity, it has been proved to be NP-

hard in the strong sense [2] for the BFSP with more than

two machines. In recent years, particle swarm algorithm,

shuffled frog leaping algorithm, artificial bee colony

Project supported by the National Natural Science Foundation of

China (Grant No.61472004 and No.61472005)

** Corresponding author. Tel. : +86 015855969300

algorithm, harmony search, intelligent optimization

algorithm etc. has been successfully applied to solute the

problems of BFSP [1-5], and it get better optimization effect

then before, but most of these studies only consider the

application of single algorithms, not with the other

advantages of the proposed algorithm, it is easy to produce

premature convergence phenomenon. Therefore, there are

further improve to the quality of algorithms need to be

processed.

Quantum-inspired Evolutionary Algorithm (QEA) is a

hybrid meta-heuristic algorithm by combining quantum

computation and evolutionary computation [6] together. It

uses quantum superposition, entanglement and coherence

through q-bit coding chromosome, introducing the quantum

rotation, crossover and mutation operator to achieve the

evolution of the population. By using the information of the

current best individual, it can update the quantum the

revolving door to accelerate the convergence of the

algorithm. The algorithm has a small population size, rapid

convergence and strong global search capability. It is easy

to realize as well. So it is widely used in automatic control,

logic circuit design, information security, and multi-

objective optimization fields [7-10].

In order to solve the BFSP effectively, a novel Co-

evolutionary Quantum Differential Algorithm (CQDA) is

proposed, which is based on QEA, by using the differential

evolution design theory [11] of quantum rotation gate and

the population evolution direction can be controlled. And

then the QEA-VNS (Variable Neighborhood Search) co-

evolutionary scheme is used to increase the algorithm's

global search ability. The simulation experimental results,

which are based on the typical examples, show that CQDA

can effectively improve the quality of the solution, and it is

suitable for large scale BFSP as well.

The paper is organized as follows. The description of

the BFSP formulation is provided in Section 2. After a brief

introduction of QGA is presented, the structure of proposed

algorithm is described in detail in Section 3 and Section 4

respectively. The experimental results are shown and

analyzed in Section 5. The concluding remarks are present

in Section 6 to end this paper.

II. D

ESCRIPTION OF BFSP

In BFSP, the general optimization goals are to

minimize the maximum common makespan, total

completion time or the total delay time. Among of them, to

minimize the maximum completion time means that the

下载后可阅读完整内容，剩余4页未读，立即下载

weixin_38647517

粉丝: 2
资源: 964

协同进化量子微分算法解决Flowshop调度问题

混合Flowshop调度问题

多机Flowshop调度问题

求解makepan最小的混合Flowshop调度问题的一种新的离散人工蜂群算法

改进协同粒子群优化算法及其在FlowShop调度中的应用.pdf

没有中间缓冲区的置换Flowshop调度问题的混合算法

混合无空闲排列Flowshop调度问题的有效迭代贪婪算法

离散的基于学习的优化算法，用于现实的Flowshop调度问题

解决批量流Flowshop调度问题的有效离散入侵杂草优化算法

模糊交货期FlowShop调度文化进化算法研究 (2009年)

具有维护活动的混合Flowshop调度问题的混合粒子群优化算法。

最新资源