Permutation-induced acyclic networks for the job shop scheduling problem |
| |
Authors: | Tamer F Abdelmaguid |
| |
Institution: | Mechanical Design and Production Department, Faculty of Engineering, Cairo University, Giza 12613, Egypt |
| |
Abstract: | In the literature of the combinatorial optimization problems, it is a commonplace to find more than one mathematical model for the same problem. The significance of a model may be measured in terms of the efficiency of the solution algorithms that can be built upon it. The purpose of this article is to present a new network model for the well known combinatorial optimization problem – the job shop scheduling problem. The new network model has similar structure as the disjunctive graph model except that it uses permutations of jobs as decision variables instead of the binary decision variables associated with the disjunctive arcs. To assess the significance of the new model, the performances of exact branch-and-bound algorithmic implementations that are based on both the new model and the disjunctive graph model are compared. |
| |
Keywords: | Job shop scheduling Disjunctive graph model Branch-and-bound Exact algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|