Parallel GRASP with path-relinking for job shop scheduling

详细信息    查看全文

• 作者：Aiex ; R.M. ; Binato ; S. ; Resende ; M.G.C.
• 关键词：Combinatorial optimization ; Job shop scheduling ; GRASP ; Path-relinking ; Probabilistic algorithm
• 刊名：Parallel Computing
• 出版年：2003
• 出版时间：April, 2003
• 年：2003
• 卷：29
• 期：4
• 页码：393-430
• 全文大小：1.63 M

文摘

In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines under certain constraints, such that the maximum completion time of the jobs is minimized. In this paper, we describe a parallel greedy randomized adaptive search procedure (GRASP) with path-relinking for the JSP. Independent and cooperative parallelization strategies are described and implemented. Computational experience on a large set of standard test problems indicates that the parallel GRASP with path-relinking finds good-quality approximate solutions of the JSP.