New Single Machine and Job-Shop Scheduling Problems with Availability Constraints
New Single Machine and Job-Shop Scheduling Problems with Availability Constraints
复制标题
DOI：
10.1007/s10951-005-6812-2
复制
发表时间：
2005-06
影响因子：
2
通讯作者：
Philippe Mauguiere;J. Billaut;J. Bouquard
中科院分区：
文献类型：
--
作者：
Philippe Mauguiere;J. Billaut;J. Bouquard
在本文中，我们处理的传统情况下的不可用性约束的调度问题的变种。在文献中，通常有两种主要的方法，第一种方法是操作可以被不可用期中断，第二种方法是操作不能被中断。我们考虑的上下文更一般;有些操作可以中断，有些则不能。此外，我们假设信息可以与操作以及不可用期相关。因此，不可用期可以使操作中断成为可能或不可能。作为该问题的一个应用，研究了带头尾的单机调度问题和车间作业调度问题。所有可能的情况下的组合进行了研究，并在审查后的国家的最先进的，分支定界算法提出来解决这些问题。最后，进行了计算实验和讨论。
In this paper we deal with variants of traditional cases of unavailability constraints in scheduling problems. In the literature, two main approaches are usually found. In the first one, operations can be interrupted by unavailability periods and in the second one, operations cannot be interrupted. The context we consider is more general; some operations can be interrupted, the others cannot. Moreover, we assume that information can be related to operations as well as to unavailability periods. Consequently an unavailability period can make possible or not the interruption of an operation. As an application to this new problem, the single machine problem with heads and tails and the job-shop scheduling problem are tackled. All combinations of possible cases are studied and after a review of the state-of-the-art, branch-and-bound algorithms are proposed to solve these problems. Finally, computational experiments are conducted and discussed.