• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theory and practice of logic programming >Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling
【24h】

Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling

机译：Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相关主题

摘要

Scheduling methods are important for effective production and logistics management, wheretasks need to be allocated and performed with limited resources. In particular, the Job-shopScheduling Problem (JSP) is a well known and challenging combinatorial optimization problemin which tasks sharing a machine are to be arranged in a sequence such that encompassingjobs can be completed as early as possible. Given that already moderately sized JSP instancescan be highly combinatorial, and neither optimal schedules nor the runtime to terminationof complete optimization methods is known, efficient approaches to approximate good-qualityschedules are of interest. In this paper, we propose problem decomposition into time windowswhose operations can be successively scheduled and optimized by means of multi-shot AnswerSet Programming (ASP) solving. From a computational perspective, decomposition aims to splithighly complex scheduling tasks into better manageable subproblems with a balanced number ofoperations so that good-quality or even optimal partial solutions can be reliably found in a smallfraction of runtime. Regarding the feasibility and quality of solutions, problem decompositionmust respect the precedence of operations within their jobs and partial schedules optimized bytime windows should yield better global solutions than obtainable in similar runtime on theentire instance. We devise and investigate a variety of decomposition strategies in terms of thenumber and size of time windows as well as heuristics for choosing their operations. Moreover, weincorporate time window overlapping and compression techniques into the iterative schedulingprocess to counteract window-wise optimization limitations restricted to partial schedules. Ourexperiments on JSP benchmark sets of several sizes show that successive optimization by multishotASP solving leads to substantially better schedules within the runtime limit than globaloptimization on the full problem, where the gap increases with the number of operations toschedule. While the obtained solution quality still remains behind a state-of-the-art ConstraintProgramming system, our multi-shot solving approach comes closer the larger the instance size,demonstrating good scalability by problem decomposition.

著录项

获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号