Scheduling Cutting Process for Large Paper Rolls

Abstract

Paper cutting is a simple process of slicing large rolls of paper, jumbo-reels, into various sub-rolls with variable widths based on demands risen by customers. Since the variability is high due to collected various orders into a pool, the process turns to be production scheduling problem, which requires optimisation so as to minimise the final remaining amount of paper wasted. The problem holds characteristics similar one-dimensional bin-packing problem to some extends and differs with some respects. This paper introduces a modelling attempt as a scheduling problem with an integer programming approach for optimisation purposes. Then, a constructive heuristic algorithm revising one of well-known approaches, called Best-fit algorithm, is introduced to solve the problem. The illustrative examples provided shows the near optimum solution provided with very low complexity.

Keywords

• Stock cutting problem, heuristic approaches, scheduling

Büyük Kağıt Rolelerinin Kesme Çizelgelemesi

Abstract

Kağıt kesimi büyük kağıt rulolarının talep doğrultusunda dilimlenmesi prosesinden ibarettir. Telebin standart dışı boyutlara sahip olması bu işlevin zorlukları arasındadır. Gelen taleplerin karşılanması amacı ile yapılan dilimleme işlemeleri kağıt zayiatının enazlanmasi konusunu önemli kılmaktadır. Bu çalışmada, basit sezgisel yöntemlerden en-iyi uygunluk algoritmasinda değişiklik yapılarak daha kısa zamanda aynı zayiat miktarını veren bir çizelgeleme algoritması tanitilarak uygulanmıştır. Sonuçlar algoritmanin başarılı olduğunu kanitlamaktadir.

Keywords

• Büyük rulo kesimi, sezgisel yaklaşımlar, çizelgeleme

References

1. Martinez-Alfaro, H., and Valenzuela-Rendon, M., ”Using Simulated Annealing with a Neighborhood Heuristic for Roll Cutting Optimization”, Computacin y Sistemas, 13(1), 87-95, (2009).
2. Martinez-Alfaro, H., and Valenzuela-Rendon, M., ”Paper Cutting Optimization Using Simulated Annealing”, Proc. of IEEE International Conference on Systems, Man and Cybernetics, 3038-3043, (2003).
3. Kolahan, F., and Abachizadeh, M., ”Optimizing Turning Parameters for Cylindrical PartsUsing Simulated Annealing Method”, International Journal of Engineering and Applied Sciences 6(3), 149-152, (2010).
4. Kenyon, C., ”Best-fit bin-packing with random order”, Proc. of the 7th annual ACM-SIAM, (1996).
5. Lodi, A., Martello, S., and Vigo, D., ”Recent advances on two-dimensional bin packing problems”, Discrete Applied Mathematics, 123(1-3), 379-396, (2002).
6. Lodi, A., Martello, S., and Monaci, M., ”Two- dimensional packing problems: A survey”, European Journal of Operational Research, 141(2), 241-252, (2002).
7. Sweeney, P. E. and Paternoster, E. R., ”Cutting and Packing Problems: A Categorized, Application- Orientated Research Bibliography”, The Journal of the Operational Research Society, 43(7), 691-706, (1992).
8. Coffman Jr, E.G., Garey, M.R., Johnson, D.S., and Tarjan, R.E., ”Performance bounds for level- oriented two-dimensional packing algorithms”, SIAM Journal on Computing, 9, 808-826, (1980).

9. Johnson, M. P., Rennick, C., and Zak, E., ”Skiving addition to the cutting stock problem in the paper industry”, SIAM Review, 39(3), 472-483,(Sep., 1997).