Flexible job-shop scheduling problem 25
• the order of operations for each job is predefined and cannot be modified
• the flexibility is total
• no preemption is allowed.
3 State-of-the-art
To solve the FJSP, many approaches have been proposed. Brucker and Schlie (1990)
were the first ones, in the literature, who studied the FJSP. In the case of two jobs, the
authors proposed an extension of the geometric approach. For FJSP with more than two
jobs, they used two types of approaches: a hierarchical approach and an integrated
approach. Barnes and Chambers (1996), Brandimarte (1993) and Paulli (1995) proposed
a hierarchical approach to solve the FJSP by decomposing it into a sequence of
subproblems with reduced difficulty. A typical decomposition is assign-then-sequence,
coming from the trivial observation that once the assignment is done, the resulting
sequencing problem is a job shop problem. The authors solved the assignment problem
using some dispatching rules, and then solved the resulting job shop problem using
different tabu search heuristics.
In Chen et al. (1999) and Mesghouni et al. (1998), the authors suggested resolving the
FJSP by a genetic algorithm. Kacem et al. (2002) proposed two new approaches to solve
the FJSP. The first one is the approach by localisation. It is developed to solve the
problem of resource allocation and build an ideal assignment model. The second one is
an evolutionary approach controlled by the assignment model. Zhang and Gen (2005)
developed a multistage operation-based genetic algorithm to deal with the problem from
a point view of dynamic programming. Meriem and Ghédira (2004) developed a Multi-
agent approach based on the tabu search method. Their underlying model is composed of
three classes of agents: job agents, resource agents and an interface agent containing the
tabu search core. Liouane et al. (2007) developed an application of the ant system
algorithms combined with a tabu search heuristic for solving the FJSP.
In Zribi et al. (2007), the authors proposed two methods to solve the flexible job shop
problem. The first type of method is hierarchical. It consists in solving the assignment
problem in a first step and then the sequencing problem in the second step. The second
type is an integrated method based on the genetic algorithms. In Pezzella et al. (2008) and
Vilcot (2007), the authors reported satisfactory results of using genetic algorithms for the
resolution of FJSP. Gao et al. (2008), proposed the hybrid genetic and variable
neighbourhood descent algorithm for this problem. Rossi and Dini (2007) studied the
FMS scheduling in a job-shop environment with routing flexibility, sequence-dependent
setup and transportation time. They developed an ant colony algorithm. In Rossi and
Boschi (2009), the authors developed a distributed-collaborative search algorithm which
hybridises genetic algorithms and ant colony optimisation for the job-shop scheduling
problem with parallel machines.
Alvarez-Valdes et al. (2005), developed an approach in two phases to solve the FJSP:
in the first phase; they built a feasible initial solution which will be improved, in the
second phase; they developed a local search method. According to the experiments and
the made tests, the authors concluded that their approach produces rough solutions in
very short run time. Hmida et al. (2010) developed a climbing depth-bounded
discrepancy search (CDDS) method to solve the FJSP with the objective of minimising
剩余17页未读，继续阅读
ShiJustin
- 粉丝: 8
- 资源: 20
我的内容管理
展开
最新资源
- C++标准程序库：权威指南
- Java解惑：奇数判断误区与改进方法
- C++编程必读：20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程：从入门到精通
- Spring3.0权威指南：JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略：从环境配置到索引创建
- 内存虚拟硬盘技术：提升电脑速度的秘密武器
- Java操作数据库：保存与显示图片到数据库及页面
- ISO14001：2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发：触发器与控制器重定向技术详解
- FPGA开发实战指南：创新设计与进阶技巧
- ShopExV4.8二次开发入门：解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
