权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Development of makespan minimization techniques involving scheduling patterns for a job shop

开发完工时间最小化技术，涉及作业车间的调度模式

基本信息

批准号：
13680522
负责人：
MORIKAWA Katsumi
金额：
$ 0.32万
依托单位：
HIROSHIMA UNIVERSITY
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680522/
关键词：
Scheduling Job shop Makespan Human scheduler Scheduling patterns

项目摘要

This study deals with makespan minimization of a job shop. The makespan is the length of a schedule and its minimization is known as a hard optimization problem. In this study we have tried to generate a minimum makespan schedule by assigning operations from time zero toward the end of the planning horizon. However the minimization of makespan using this method is not so easy as it is often difficult to estimate the effect of assigning one candidate operation among conflicting operations on the makespan with enough accuracy, especially in earlier decision stages. To alleviate this difficulty we focus on the human scheduler's judgments. A person having extensive knowledge of scheduling theory and having experience in scheduling decisions can often find a better schedule by modifying an initial schedule with the aid of an interactive scheduling support system. In this study we first extracted typical rescheduling patterns of a graduate student experimentally, then constructed a procedure based on these patterns, and combined it with the active schedule generation algorithm of Giffler and Thompson. Numerical experiments showed favorable results of the proposed approach. To enhance the proposed approach, the Lagrangean relaxation technique was also investigated as a guide of selecting the most promising operation. This approach often showed better results than the lower-bound-based selection. Our underlying optimization mechanism is a depth-first branch and bound method, and this method often consumes a long computation time. By collecting the reasons of unsuccessful conditions from all immediate child nodes, it may be possible to go to a parent node two or more levels above without losing optimality of the search. Although managing the search history requires additional computations, this search method realized an effective search in some problem instances.

本文研究了作业车间的最大完工时间最小化问题。最大时间跨度是一个计划的长度，它的最小化被称为一个难优化问题。在本研究中，我们试图通过分配从时间0到计划范围结束的操作来生成最小完工时间计划。然而，使用这种方法最小化makespan并不容易，因为通常很难准确地估计在冲突操作中分配一个候选操作对makespan的影响，特别是在早期决策阶段。为了减轻这种困难，我们将重点放在人类调度程序的判断上。一个具有丰富的调度理论知识和调度决策经验的人通常可以在交互式调度支持系统的帮助下通过修改初始调度来找到更好的调度。本文首先通过实验提取了一名研究生的典型重调度模式，在此基础上构建了一个程序，并将其与Giffler和Thompson的主动调度生成算法相结合。数值实验表明了该方法的良好效果。为了加强所提出的方法，还研究了拉格朗日松弛技术作为选择最有前途的操作的指导。这种方法通常比基于下限的选择显示更好的结果。我们的底层优化机制是一种深度优先的分支定界方法，这种方法通常会消耗很长的计算时间。通过从所有直接子节点收集不成功条件的原因，可以在不失去搜索最优性的情况下转到比它高两层或更多层的父节点。虽然管理搜索历史需要额外的计算，但该搜索方法在某些问题实例中实现了有效的搜索。