标题: 以三阶粒子群最佳化演算法搭配作业序表达法解弹性零工式排程问题
A Three-Phase PSO Algorithm with an Operation-Sequence-Based Chromosome Representation for Scheduling Flexible Job Shops
作者: 赖佳卉
Lai, Chia-Hui
巫木诚
Wu, Muh-Cherng
工业工程与管理学系
关键字: 弹性零工式排程问题;粒子群演算法;巨集启发式演算法;解表达法;flexible job-shop scheduling problem;particle swarm optimization algorithm;meta-heuristic algorithms;solution representation
公开日期: 2011
摘要: 本论文研究议题为弹性零工式排程问题(Flexible Job-shop Scheduling Problem, FJSP)。FJSP包含两项子决策:(1)作业指派(operation-to-machine assignment),(2)作业排序(operation sequencing for each machine)。过去研究已证明FJSP的复杂度为NP-hard,以往学者透过发展各种不同巨集启发式演算法(meta-heuristic algorithms)来求解。本论文以粒子群最佳化演算法(Particle Swarm Optimization, PSO)的架构搭配一个新的染色体表达法(简称Sop),发展出一新的三阶演算法(称为PSO_Sop)来求解FJSP。染色体表达法即是指解的表达法,Sop表达法的概念是排序所有作业,即一条染色体就是一组特定的作业排序(a particular sequence of operations)。本论文提出启发式规则(heuristic rule),藉此导出作业排序染色体其相对应的作业指派子决策。本论文求解目标为最小化最大完工时间(makespan)。
This research is concerned with the scheduling of a flexible job-shop problem (called FJSP), which involves two sub-decisions: (1) operation-to-machine assignment (2) operation sequencing for each machine. Most prior studies proposed meta-heuristic algorithms for the FJSP problem. This research proposes a new solution representation (called Sop), which is intended to model a particular sequence for all operations. Given a particular Sop, by a heuristic rule, we can obtain its two corresponding sub-decisions; which in turn represents a particular scheduling solution. Based on the Sop representation, this research adopts the existing architecture of particle swarm optimization (PSO) algorithm and develops a three phases meta-heuristic algorithm (called PSO_ Sop) to solve the FJSP problem.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079933511
http://hdl.handle.net/11536/50074
显示于类别:Thesis