مدل های ریاضی برای مشکلات برنامه ریزی تولید کارگاهی با مسیریابی و انعطاف پذیری پلان فرایند

As a result of rapid developments in production technologies in recent years, flexible job-shop scheduling problems have become increasingly significant. This paper deals with two NP-hard optimization problems: flexible job-shop scheduling problems (FJSPs) that encompass routing and sequencing sub-problems, and the FJSPs with process plan flexibility (FJSP-PPFs) that additionally include the process plan selection sub-problem. The study is carried out in two steps. In the first step, a mixed-integer linear programming model (MILP-1) is developed for FJSPs and compared to an alternative model in the literature (Model F) in terms of computational efficiency. In the second step, one other mixed-integer linear programming model, a modification of MILP-1, for the FJSP-PPFs is presented along with its computational results on hypothetically generated test problems.

Scheduling may broadly be defined as the allocation of resources to tasks over time in such a way that a predefined performance measure is optimized. From the viewpoint of production scheduling, the resources and tasks are commonly referred to as machines and jobs and the commonly used performance measure is the completion times of jobs. This problem has been extensively researched since the early 1950’s. A comprehensive survey of literature on scheduling problems can be found in Graves [1], Lawler et al. [2], and Lee et al. [3]. The classical job-shop scheduling problem (JSP) consists of a set of independent jobs, each having its own processing order through a set of machines. Each job has an ordered set of operations, each of which must be processed on a predefined machine. The problem, known to be strongly NP-hard, is to sequence operations on the machines so that the maximum completion time over all jobs (Cmax) is minimized. Considerable research has been devoted to this problem in the literature. An overview of history and main techniques used along with their reported results on the available benchmarking problems for JSP can be found in Jain and Meeran [4]. The JSP assumes only one available machine for each operation and one feasible process plan (operation sequence) for each job. It is common, however, in real-world scheduling problems to have a wider space for choices. Typically, in a manufacturing setting there are choices to be made in scheduling from among alternative machines on which to perform an operation or from among alternative process plans of a job through a factory [5]. This paper considers two extensions to the JSP, i.e., routing flexibility and process plan flexibility. The former implies the availability of alternative machines for each operation, and the latter the availability of alternative process plans for each job. The flexible job-shop scheduling problem (FJSP) is an extension of JSP in that it incorporates the routing flexibility. Due to complications resulting from the addition of routing flexibility to the already difficult JSP, researchers have focused on metaheuristic approaches to solve the FJSP. Among these are the evolutionary algorithms [6], [7] and [8], tabu search [9], [10], [11], [12] and [13], simulated annealing [14] and [15], ant colony [16] and hybrid approaches [17], [18], [19], [20], [21] and [22]. The FJSP with process plan flexibility (FJSP-PPF) refers to a more complicated decision problem where jobs can have alternative process plans. The literature for this problem is quite limited: evolutionary algorithms [23], [24] and [25], tabu search [26], simulated annealing [27], and constraint-directed techniques [5]. As for the mathematical models, the initial formulations of scheduling may be traced back to 1960’s. Shapiro [28] has presented mathematical programming models and solution methods that have been applied to several types of production planning and scheduling problems. Pan [29] has provided a review and comparison of mixed-integer linear programming (MILP) formulations for job-shop, flow-shop and permutation flow-shop scheduling problems described in the literature. Kim and Egbelu [30] have developed a MILP model for JSP, where each job has predetermined alternative process plans. They have also presented two algorithms, each consisting of three modules, i.e., selecting a process plan combination, computing the lower bound on makespan, and scheduling. While the scheduling module of the first algorithm depends on the developed MILP model, that of the second algorithm employs earliest completion time (ECT) dispatching rule. Brandimarte [31] has addressed a multi-objective scheduling problem with process plan flexibility and proposed a hierarchical approach, based on a decomposition into machine loading and scheduling sub-problems. Brandimarte’s paper deals only with the machine loading problem (selecting a process plan for each job and assigning operations to the machines). The problem is formulated as a bicriterion integer programming model and two different heuristics are proposed, one based on surrogate duality theory and the other based on a genetic descent algorithm. Low and Wu [14] have addressed the FJSP with the objective of minimizing total tardiness, under setup time consideration. The problem presented as an extended disjunctive graph has been formulated as a mixed-integer programming model, and then quadratic terms in the constraints have been linearized. A simulated annealing-based heuristic has been proposed to solve the problem. The model presented in Low and Wu [14] has been extended to a multi-objective model by Low et al. [19]. Thomalla [32] has proposed a discrete-time integer programming model for the FJSP with the objective of minimizing the sum of the weighted quadratic tardiness of the jobs and developed an algorithm based on Lagrangian relaxation. Choi and Choi [33] have presented a MILP model for the FJSP with sequence-dependent setups, along with a local search algorithm that uses a dispatching rule to obtain an upper bound on the makespan of a subproblem. Gomes et al. [34] have addressed the FJSP with limited intermediate buffers and developed a multi-objective discrete time model that divides the scheduling horizon into a number of intervals of equal duration. This model has subsequently been generalized to account for re-circulation, where jobs may visit certain machine groups more than once. Gao et al. [18] have formulated the FJSP with non-fixed machine availability constraints, where each machine is subject to an arbitrary number of preventive maintenance tasks. To solve this problem, they have proposed a hybrid genetic algorithm. Fattahi et al. [20] have developed a mixed-integer programming model and also six hybrid searching structures that differ in accordance with the searching approaches and heuristics they have used to solve FJSPs. Lee et al. [23] have presented a mathematical model for FJSP-PPF in which each customer order has a due date and outsourcing is available. To solve the model, a genetic algorithm-based heuristic approach has been developed. In this paper, a well-known model, which is developed by Manne [35] for JSPs, is modified with the purpose of enabling it to solve the FJSPs. The resulting model is referred to as MILP-1. A mechanism is then incorporated into MILP-1 to take care of the FJSP-PPFs. The resulting model is referred to as MILP-2. In our search in the literature for the mathematical modelling approaches, all except one of the models we came across are different variations of the scheduling problems either with routing or with process plan flexibility, but not both. The only exception is the model developed by Lee et al. [23]. However, this model is not comparable to MILP-2. Since customer due dates and outsourcing are incorporated into the model, it does not address the FJSP-PPF as described in Section 2. The remainder of this paper is organized as follows: in Section 2, a formal problem description is given. In Section 3, MILP-1 is presented and compared with the model developed by Fattahi et al. [20]. Section 4 is devoted to the presentation of MILP-2 and to its computational results on test problems. Concluding remarks are made in Section 5.

This study started with the FJSP, the generalized form of the JSP. In the first step, a mixed-integer linear programming model (MILP-1) is developed for the FJSPs. MILP-1 is then compared to the only alternative model we found in the literature and its superiority over Model F in terms of model size, CPU time and Cmax value is displayed. In the second step, process plan flexibility is incorporated into FJSP, and MILP-1 is modified accordingly to give rise to MILP-2, for which there appears to be no comparable mathematical model in the literature. Hypothetical test problems that involve routing and process plan flexibility are used for testing MILP-2. The computational results on a variety of test problems with different sizes and flexibility levels are presented and evaluated. Makespan is adopted as the single performance measure in MILP-1 due to the fact that it is the single measure used in the model that MILP-1 is compared with in this paper, namely Model F. Since it is an extension of MILP-1, we chose to retain the makespan as the single measure in MILP-2. It must however be mentioned that additional measures such as total tardiness, the number of tardy jobs and the load balance of the machines can readily be incorporated into MILP-2. The authors of this paper are planning as a future study to develop a general framework model that embodies sequence-dependent setup times and process plan costs along with routing and process plan