Job shop scheduling with unit time operations under resource constraints and release dates |
| |
Institution: | Universidade Federal do Rio de Janeiro, Núcleo de Computação Electrônica and Instituto de Matemática Rio de Janeiro, Brazil |
| |
Abstract: | We consider the problem of job shop scheduling with m machines and n jobs Ji, each consisting of li unit time operations. There are s distinct resources Rh and a quantity qh available of each one. The execution of the j-th operation of Ji requires the presence of uijh units of Rh, 1 ≤i≤n, 1 ≤j≤li, and 1 ≤h≤s. In addition, each Ji has a release date ri, that is Ji cannot start before time ri. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let l=max{li} and u=|{uijh}|. If m, u and l are fixed, then both algorithms terminate within polynomial time. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|