Job-shop scheduling with limited capacity buffers |
| |
Authors: | Peter Brucker Silvia Heitmann Johann Hurink Tim Nieberg |
| |
Affiliation: | (1) Department of Mathematics/Informatics, University of Osnabrück, Albrechtstr. 28, 49069 Osnabrück, Germany;(2) Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands |
| |
Abstract: | In this paper we investigate job-shop problems where limited capacity buffers to store jobs in non-processing periods are
present. In such a problem setting, after finishing processing on a machine, a job either directly has to be processed on
the following machine or it has to be stored in a prespecified buffer. If the buffer is completely occupied the job may wait
on its current machine but blocks this machine for other jobs. Besides a general buffer model, also specific configurations
are considered. The aim of this paper is to find a compact representation of solutions for the jobshop problem with buffers.
In contrast to the classical job-shop problem, where a solution may be given by the sequences of the jobs on the machines,
now also the buffers have to be incorporated in the solution representation. In a first part, two such representations are
proposed, one which is achieved by adapting the alternative graph model and a second which is based on the disjunctive graph
model. In a second part, it is investigated whether the given solution representation can be simplified for specific buffer
configurations. For the general buffer configuration it is shown that an incorporation of the buffers in the solution representation
is necessary, whereas for specific buffer configurations possible simplifications are presented. |
| |
Keywords: | Job-shop problem Buffer Disjunctive graph Alternative graph |
本文献已被 SpringerLink 等数据库收录! |
|