Archives > Volume 13 | Number 4 | December 2018 > pp 373–388
Advances in Production Engineering & Management
Volume 13 | Number 4 | December 2018 | pp 373–388
Flexible job shop scheduling using zero-suppressed binary decision diagrams
Meolic, R.; Brezočnik, Z.
ABSTRACT AND REFERENCES (PDF) |
FULL ARTICLE TEXT (PDF)
A B S T R A C T
A flexible job shop scheduling problem (FJSP) is a widely studied NP-hard combinatorial problem. Its goal is to optimise the production plans for simultaneously produced parts, where each part production consists of executing various operations. Each operation can be executed on several, or even all, available machines. A distinctive subproblem of FJSP is the identification of feasible solutions. A feasible solution is an allocation plan (i.e. assignment of a machine to a particular operation of a part to be produced) yielding an execution schedule satisfying the given resource constraints. FJSP is applied primarily in manufacturing systems, but it can be used to optimise Internet traffic, cloud computing, and other resource scheduling problems as well. So far, the exact methods for solving FJSP have not been considered attractive, since they seemed incapable of coping with real-size problems. This paper proposes a novel exact approach to solving FJSP which can find and count out all schedules of relatively large systems. The approach is successful due to the power of a special data structure called zero-suppressed binary decision diagrams to represent and manipulate the set of all feasible solutions efficiently. All the algorithms are implemented and tested by using our free Binary Decision Diagram package called Biddy.
A R T I C L E I N F O
Keywords • Process planning; Exact optimization; Flexible job shop scheduling; Unate cube set algebra; Zero-suppressed binary decision diagram
Corresponding author • Brezočnik, Z.
Article history • Received 17 June 2018, Revised 13 November 2018, Accepted 15 November 2018
Published on-line • 19 November 2018
E X P O R T C I T A T I O N
» RIS format (EndNote, ProCite, RefWorks, and most other reference management software)
» BibTeX (JabRef, BibDesk, and other BibTeX-specific software)
» Plain text
< PREVIOUS ISSUE PAPER
NEXT PAPER >