Task allocation strategy of garment production based on improved integer Programming (Стратегия распределения задач при

Task allocation strategy of garment production based on improved integer Programming (Стратегия распределения задач при производстве одежды, основанная на программировании целых чисел)

XUEWEI JIANG, ANHUA ZHONG (Wuhan Textile University, Китай)

Абстракт: Разумное распределение задач является очень важным для производства одежды, непосредственно влияющим на стоимость производственных затрат и эффективность производства. В случае задач, которые должны быть решены в определенное время, предприятие должно оптимизировать распределение задач и минимизировать затраты. В соответствии с реальными условиями производства в этой работе разработана математическая модель для программирования и предложен улучшенный алгоритм. Экспериментально доказано, что эта модель и алгоритм позволяют оптимизировать систему производства и показана ее эффективность и адекватность.

Ключевые слова: производство одежды, стратегия распределения задач, линейное программирование целых чисел, ветвь, предел.

In order to complete the production task at the least cost and the shortest time, the manpower, material resources and capital of garment enterprises should be made unified plan[1]. This requires that garment enterprise should pay more attention to task allocation of garment production, that is to say reasonable allocation strategy is directly related to their enterprise cost and production efficiency. Task allocation problem has been widely studied in past, and is great value in operations research and engineering application[2]. Integer programming is one kind of the method that distributing resources very effectively, especially to the produce task of garment enterprise. The main achievements of the method are the three algorithms that branch and bound algorithm, implicit enumeration and Hungarian algorithm. The implicit enumeration and Hungarian algorithm are 0-1 programming, and it is not suitable to our research problem. Therefore, the branch and bound algorithm has been selected to study our problem, and we have improved this algorithm in this work.

Task allocation problem is to reasonably assign various tasks to each workshop. The purpose is to minimize the cost under the condition in which the tasks can be completed on time[3]. The optimize mode is established according to the least cost and transform to integral linear programming on above thought.

m n

min f = ZZCijXj

t=\ j=\ n

Z hx

j=1

n

Z x

l i=1

In this model, i and j indicate the workshop and task sequence respectively, cij is the production cost of task j assigned to workshop i, xij is assigned tasks j to workshop i, tij is the processing time for task j performed by workshop i, T is time of delivery, and Taj denotes the number task j. The minimize function ensures that the cost is minimal, the second equation control the task can be finished on time, and the third equation is the most important guarantees for the successful completion of the project tasks.

How to select the branch node has obvious effects on the branch and bound method. The depth-first search and breadth-first search are usually adopted to search the branch node, but the quality of integer solutions is not high and the searching time is long. Therefore, we improved the algorithm, the non-integer variables with largest difference from integer value will be considered as branch. This improved method not only enhance the efficiency of branch node searching but also can get the optimal integer solution as far as possible.

The effectiveness and accuracy of our model with improved algorithm are clearly demonstrated by an experiment. One garment enterprise has four production workshop, three styles clothing are required to make and the numbers of them are 180, 200 and 150 respectively. The manufacturing cost and the single production time of each style made in different workshop are shown in table 1, the delivery period of these clothing is 3000 minutes.

The above data is putted into our model, the improved algorithm is used to calculate task allocation. Results show that 60 pieces of clothing of style 1 are made by workshop 2 and 120 pieces are made by workshop 3, workshop 1 and 2 are responsible for 124 and 76 pieces of clothing of style 2, and 150 pieces of clothing of style 3 are entirely produced by workshop 4. To complete this batch of clothing, the minimum cost is 4060 dollar, this value is lower than our previous result of studying.

Fig. 1. Processing time of each workshop 188

The total processing time of each workshop is shown in Fig. 1, all of them are controlled in the delivery period, and the tasks allocated to every workshop are relatively balance. The numbers of task for workshop 3 and 4 are same that equal to 3000 minutes as extreme as the delivery period, this value is about 500 minutes more than workshop 1 and 2. This is mainly to ensure the cost minimum. For example, putting style 3 in workshop 4 to make, the cost is minimum, and style 3 should be made by workshop 4 as much as possible. Therefore, the total processing time of workshop 4 is 3000 minutes. On the basis of these analysis, we think that this model and the improved algorithm for task allocation of garment production is very effective and feasible.

REFERENCE:

[1] M. Ben Dhaou, and D. Fayard, in Applications of Combinatorial Optimization (John Wiley & Sons, Inc., 2013), pp. 23.

[2] J. Li, and Y. Shi, International Transactions in Operational Research 8, 497 (2001).

[3] D.-S. Chen, R. G. Batson, and Y. Dang, in Applied Integer Programming (John Wiley & Sons, Inc., 2009), pp. 411.

УДК 687.157:677.027.65:687.023.001.5

Количество показов: 509