شبکه های غیر قابل چرخش ناشی از جابجایی برای مشکل زمان بندی تولید کارگاهی

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.

The job shop scheduling problem (JSSP) is concerned with sequencing a set of jobs, J, on a set of technologically different machines or work centers, M, each is capable of processing at most one job at a time. Jobs follow dissimilar processing routes among the machines, and a job cannot be processed on more than one machine simultaneously. Furthermore, preemption is not allowed, and a job is permitted to have multiple visits to any machine. This article addresses the static, deterministic version of the problem in which raw materials for all jobs are assumed to be ready for processing at the beginning of the schedule, and the processing times are deterministic. The JSSP arises in low-volume production systems in which products are made to order. In these production systems, jobs usually differ considerably in their processing sequences and times. Solving the JSSP is particularly important for the efficient utilization of production resources and for satisfying due dates. However, the JSSP is fairly complex. Even for the small case of three jobs and three machines, the JSSP, with the objective of minimizing the makespan, is known to be NP-hard (Sotskov and Shakhlevich [1]). Earlier complexity results for the JSSP are provided by Garey et al. [2]. This high level of complexity demands continuous efforts for developing efficient solution approaches.

The purpose of this article is to present a new network model for the job shop scheduling problem. The new network model has a very similar structure as the traditional disjunctive graph model, except that job permutation on machines are used as decision variables instead of the disjunctive binary decision variables. In the new model, job permutations are interpreted into directed arcs in the network allowing for the use of the critical path length algorithm to evaluate the makespan of the schedule represented by given job permutations, and consequently evaluating lower bounds in a similar way as in the disjunctive graph model. The apparent benefit of using the new network model over the traditional disjunctive graph model is that the size of the search space for the decision variables is significantly reduced. This reduction in the size of the search space suggests that the worst-case performance of an exact solution algorithm that is based on the new model will be better than that of the disjunctive graph model. However, this is not enough to claim the superiority of the new model. In order to assess the significance of the new model from the side of the algorithmic implementation, the performance of simple exact branch-and-bound algorithmic implementations that are based on both network models are compared. The experimental results show that, on average, the performance of the branch-and-bound implementation that is based on the disjunctive graph model is better than that of the PIAN-based implementation. Nevertheless, there are some merits in the new model that allow it to achieve a proven optimal solution in much less computational time. As part of future research, additional properties of the PIAN model need to be investigated. Such properties might help in speeding up the solution algorithms and might allow for implementing more sophisticated techniques similar to those found in the literature of the disjunctive graph model such as immediate selections.