Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1642
Type: Relatório
Title: Job shop scheduling with unit time operations under resource constraints and release dates
Author(s)/Inventor(s): Szwarcfiter, Jayme Luiz
Abstract: Considera-se o problema de job shop scheduling com m máquinas e n jobs Ji, cada qual consistindo de ei operações de tempo unitário. Existem s recursos distintos Rh, cada um disponível em quantidade qh. A execução da j-ésima operação de Ji requer a presença de u ijh unidades de R h, 1≤i≤n, 1≤j≤e i e 1≤h≤s. Em adição, cada Ji possui uma data de liberação r i. São descritos algoritmos para determinar schedules possuindo comprimento ou tempo médio de término mínimos. Seja e =max{e i} e u=| {u ijh}|. Se m, s, u e e são fixos então ambos os algoritmos terminam em tempo polinomial.
Abstract: We consider the problem of job shop scheduling with m machinesand n jobs J i, each consisting of ei unit time operations. There are s distinct resources R h and a quantity q h avaiable of each one. The execution of the j-th operation of Ji requires the presence of u ijh units of R h, 1≤i≤n, 1≤j≤ei and 1≤h≤s. I addition, ach Ji has a release date r i, that is J i cannot start before time r i. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let e=max{e i} and u=| {u ijh}|. If m., s, u and e are fixed then both algorithms terminate within polynomial time.
Keywords: Escalonamento
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Production unit: Instituto Tércio Pacitti de Aplicações e Pesquisas Computacionais
In: Relatório Técnico NCE
Issue: 0185
Issue Date: 30-Sep-1985
Publisher country: Brasil
Language: eng
Right access: Acesso Aberto
Citation: SZWARCFITER, J. L. Job shop scheduling with unit time operations under resource constraints and release dates. Rio de Janeiro: NCE, UFRJ, 1985. 11 p. (Relatório Técnico, 01/85)
Appears in Collections:Relatórios Técnicos e de Pesquisa

Files in This Item:
File Description SizeFormat 
01_85_000040319.pdf982,39 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.