Possibilities to optimise scheduling production.

Cociu, Nicolae ; Taroata, Anghel ; Taucean, Ilie Mihai 等

Abstract: The paper examines some problems of scheduling production: n products on one machine, n products on two machines, n products on m machines. For scheduling of n products on one machine, we need reduce computation time by using heuristic algorithm that generally does not provide optimal solutions, but sub-optimal solutions, in the vicinity of optimal solution. Production scheduling of n products on two machines can be done with Johnson's algorithm. Some heuristic algorithms are presented, optimization criteria, priority rules, and an example of mathematical model for scheduling n products on m machines. The complexity of scheduling production problem arise from production conditions of each industrial enterprise

Key words: scheduling production, ordering production, linear programming, heuristic algorithm

1. INTRODUCTION

Production scheduling is an important component of production management. It sets scheduling production deployment space (sections, workshops, working groups, jobs) and time (month, week, day, change, time) of production tasks (Andreica, 1998). The complexity of scheduling production problem arises from production conditions of each industrial enterprise: specific technological nature of the product and type of production.

The specific production technology influences the way scheduling production of objects in space and in time work, the degree of specialization of production structures and the degree of continuity of production.

The nature of the product has influence on the structural complexity of scheduling production of product and constructive relations, how to assemble product components, the number and nature of the product components.

The type of production affects the entire production scheduling. For mass production and large series scheduling production is relatively simple. Production scheduling for continuous processes is relatively simple, but for discontinuous processes can be very complex (Cociu, 1999).

2. POSSIBILITIES TO OPTIMIZE PRODUCTION SCHEDULES

2.1 Manufacturing scheduling

Production scheduling methods can use or not an optimization criteria. Several optimization criteria are (Taucean, 2008) (Nemeti, 1975):

--maximizing output;

--maximum use of production capacity;

--minimizing the consumption of raw materials;

--minimizing production cycle (a total duration of operations);

--minimizing the unfinished production;

--minimizing the time of stagnation of the equipment;

--minimize the volume of capital.

Ordering of manufacturing is part of scheduling production. Ordering of manufacturing means determining optimal processing order (to minimize the total processing time, minimizing the total time of adjustment, minimizing time of stagnation of the equipments, etc.) of n products on m machines. In ordering of manufacture activity it can be used or no optimization methods.

2.2 Production scheduling of n products on one machine

Production scheduling of n products on one machine, m=1, can be done using heuristics algorithms, such as NB (Next Best) and NB with variable origin. In a complex machine that requires a long adjustment to switch from processing one type of piece to another, the question of determining the optimal sequence of n pieces scheduled to be processed on that machine.

Optimization is understood in the sense of minimizing the time required for all settings. Let [t.sub.ij] be the total time adjustment processing equipment after the play to begin processing [P.sub.i] [P.sub.j] piece. The product is similar to previous [P.sub.i] [P.sub.j] next product, the less time will be [t.sub.ij]. Values hold no meaning as would the same product after himself. Are possible n! = 1.2..... n the n processing sequence of parts and is not cost effective in terms of computing time to take all possible permutations of the n pieces. Reduce computation time by using heuristic algorithm generally does not provide optimal solutions, but sub-optimal solutions, in the vicinity of optimal solution. NB algorithm is based on reasoning: the next piece [P.sub.j] resulting from choosing the less time adjusting the machine after executing the previous piece [P.sub.i]. Determine positive sequence, the optimum or near optimum solution with total control time [T.sub.1].

Taking as a criterion for choosing the maximum control algorithm in NB or NB algorithm with variable origin, we obtain the sequence of processing the worst, unwanted non-optimal. Whether this time equal to [T.sub.2]. Admission is determined as the time interval T total control.

T [member of] [[T.sub.1], [T.sub.2]] (1)

2.3 Production scheduling of n products on two machines

Production scheduling of n products on two machine, m=2, can be done with Johnson's algorithm. The scheduling is intended to minimize the total processing time on both machines. On two machines A and B should be processed in different parts, the workflow is in the order A, B. Each piece is Pi times the processing on the two machines give the vector ([a.sub.i], [b.sub.i]), i = 1, 2 ..., n. It is considered that during the preparation of the paper is zero or if there is the same for each piece [P.sub.i], regardless of previous work and therefore can be included in processing time. If the transportation time from machine A to machine B is zero, [t.sub.i] = 0, i = 1, 2, ..., n, using Johnson's algorithm directly. If the transportation time from machine A to machine B is different from zero [t.sub.i] > 0, i = 1, 2, ..., n, is calculated:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Johnson's algorithm is used for processing times ([a'.sub.i], [b'.sub.i]), i = 1, 2, ..., n, resulting in initial ordering problem. If [a.sub.i] [member of] [[c.sub.i], [d.sub.i]], [b.sub.i] [member of] [[e.sub.i], [f.sub.i]], one can determine the range of total processing time frame T. Johnson's algorithm is used for processing times ([c.sub.i], [e.sub.i]), i = 1, 2, ..., n, resulting in total processing time [T.sub.1], then the processing time ([d.sub.i], [f.sub.i]), i = 1, 2, ..., n, resulting in time [T.sub.2].

T [member of] [[T.sub.1], [T.sub.2]] (3)

2.4 Scheduling of n pieces on m machines (m [greater than or equal to] 3)

Scheduling to manufacture parts for 3 machines n, m [greater than or equal to] 3, A, B, C, in order to, B, C, with the times of processing thrown by vector ([a.sub.i], [b.sub.i], [c.sub.i]), i = 1, 2, ..., n, if verified one of the conditions (4) or (5) is reduced to pieces n on authorization to m = 2 algorithm machines with Johnson.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

We calculated relationship (6).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

It is Johnson algorithm used when considering n parts on two machines A and B' of the processing time give the vector ([a'.sub.i], [b'.sub.i]), i = 1, 2, ..., n, resulting sequence of optimal processing of initial problem.

The general production scheduling of n pieces on m = 3 machines if it is not checked none of the conditions (4) or (5) is more complicated.

Production scheduling of n products on m machines, m [greater than or equal to] 3, can theoretically solve a problem of disjunctive linear programming, which has the mathematical formula (7):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (7)

3. LIMITATIONS AND FUTURE RESEARCH

Solving the problem of data relations (7) is reduced to resolve the problems [2.sup.p] linear programming and the choice between them that the objective function f has the lower value. To solve those problems [2.sup.p] linear programming it may be used computer programs, but the calculation can be great.

For example, for a company is likely to exist in the model (7) p = 10 disjunctive conditions, so in this case should be resolved [2.sup.10] = 1024 problems of linear programming. Because of the large quantity of calculations, in practice, according to the values of concrete n and m, and the terms of concrete undertaking, using heuristic algorithms, generally a sub-optimal solution is obtained in the neighborhood of optimal solution.

For production scheduling through heuristic algorithms we can use rules of priority, such as:

--the order arrival, first in first out (FIFO);

--the most expensive benchmark;

--the greatest time of execution;

--the smallest time performance;

--the greatest time total processing;

--the smallest total time of processing; the most important order;

--the greatest time for operations processing for prior;

--the smallest time for operations processing for prior; last come first served (Last In First Out--LIFO).

None of these rules (or other rules) has a clear superiority over others; their use depends on the company. We may use combined priority rules for scheduling, the type content, disjunctive, additive, multiplicative or multi-criteria. The use of indicators priority objective function is not specified. If we obtained several solutions authorization acceptable we can select the best solution using multi-criteria decision (Filip, 2007).

Production scheduling on several machines can achieved good results through heuristic methods, such as: sequential programming, downstream programming, and upstream programming. Evaluation of scheduling efficacy achieved can be done by respecting deadlines and if there are periods exceeded it must take into account the penalties (Taroata & Hoanca, 2000).

4. CONCLUSIONS

Production scheduling is an important component of production management. The complexity of scheduling production problem is great and in a company we need to have a solution very rapidly, so we have to be prepared.

The use of methods to optimize the production scheduling helped to increase competitiveness of a company. In general, scheduling manufacture of n products on m machines, m [greater than or equal to] 3, is complex and requires many calculations, and for that reason the industrial practice should be achieved by heuristic algorithms giving an optimal or sub-optimal solution.

5. REFERENCES

Andreica, M. et al. (1998). Quantitative Methods in Management (in Romanian), Economical Publishing House, ISBN 973-590-027-0, Bucuresti

Cociu, N. (1999). Optimization in Conceiving and Exploiting the Production Systems (in Romanian), Eurobit Publishing House, ISBN 973-9201-15-6, Timisoara

Filip, F. G. (2007). Support Systems for Decisions (in Romanian), Technical Publishing House, ISBN 978-973-312-308-8, Bucuresti

Nemeti, L. (1975). Time Programming of the Manufacturing (in Romanian), Dacia Publishing House, Cluj-Napoca

Taucean, I. (2008). Production Management (in Romanian), Solness Publishing House, ISBN 978-973-729-136-3, Timisoara

Taroata, A. & Hoanca, R. (2000). Engineering and Management of Production Systems (in Romanian), Solness Publishing House, ISBN 973-99226-8-6, Timisoara