برنامه ریزی تولید کارگاهی با برنامه های فرآیند جایگزین

Successful implementation of automated manufacturing systems highly depends on effective utilization of resources. Efficient scheduling algorithms for alternative process plans may increase the throughput rate and guarantee a reasonable return on investment. This paper investigates an optimization methodology for scheduling jobs in a just-in-time environment. We consider the non-preemptive case where each job consists of a distinct number of operations to be processed in a specified order. Each operation has to be processed on one of a set of resources (e.g. machines) with possibly different efficiency and hence processing time. The objective is to minimize the sum of the weighted quadratic tardiness of the jobs. We obtain a fast near-optimal algorithm with guaranteed bounds for the distance to the optimum by using Lagrangian relaxation and show that just one relaxation suffices.

Scheduling in a just-in-time environment is considered one of the most important resource planning issues in a production system with varying products and small lots. Increasing computer support in industrial practice will enable the flexibilization of production towards alternative machines. But even small-sized problems need time-consuming enumeration to find the optimum, moreover if there exist alternative process plans. It is unlikely that a polynomial time algorithm for finding the optimum exists, as except for special cases scheduling problems are NP-complete. Therefore, we present an algorithm that finds a good solution, whose computational effort grows just (pseudo-) linear in the number of operations and machines and supplies a lower bound as well. If the processing times required for the operations are within a reasonable range, a reaction to a machine breakdown should be achievable in real time, especially if the algorithm is parallelized [1]. To reduce the response time, the relaxed problems for the jobs may be solved in parallel, as they are independent. The paper is organized as follows: Section 2 contains a short literature review and other approaches to the problem. The model description and a constrained discrete-time integer optimization formulation of the problem is presented in Section 3. Section 4 describes the Lagrangian relaxation technique, the solution of the subproblems, the modification of the multipliers via a subgradient technique and the heuristic to get a feasible solution. Test results are presented in Section 5 and the correctness of the algorithm is shown in the appendix.