V-shop scheduling |
| |
Authors: | V. Lev I. Adiri |
| |
Affiliation: | Technion-Israel Institute of Technology, Faculty of Industrial Engineering and Management, Technion City, Haifa 32 000, Israel |
| |
Abstract: | This paper deals with V-shop scheduling where the route by which a job passes through the machines is: M1 → M2 → ? → Mm?1 → Mm → Mm?1 → ? → M2 → M1. Flowshop scheduling is a special case of V-shop. The two-machine, minimum schedule length V-shop scheduling problem is proved to be binary NP-complete. Efficient solvable algorithms are presented for some simple special cases of NP-complete V-shop problems; specifically n/2/V/Cmax with a dominating machine and n/m/V, tij = 1/(Cmax ∩ ΣCi). n/m/V/Cmax, m?2, with an increasing series of dominating machines is discussed. |
| |
Keywords: | Deterministic scheduling |
本文献已被 ScienceDirect 等数据库收录! |
|