基于EPFF算法的下料問題模型

徐標，陳昊，安佰玲

淮北師范大學 數學科學學院，安徽 淮北 235000

基于EPFF算法的下料問題模型

徐標，陳昊，安佰玲

淮北師范大學 數學科學學院，安徽 淮北 235000

1 問題重述

原料下料問題是企業生產中最為重要的問題之一。原材料利用率的高低直接反映著企業的生產水平，也是影響企業經濟效益的主要因素之一，同時切割模式的單一化也有利于降低成本，提高生產率。因而提高原料利用率，減少切割方式對我國經濟發展具有特別重要的意義。

“下料問題”是把相同形狀的一些原材料分割加工成若干個不同規格大小的零件的問題，此類問題在工程技術和工業生產中有著重要和廣泛的應用。

對單一原材料下料問題[1]進行探討；設此種原材料是長度為L，寬度為W的長方形，現有這種長方形原料一批，要將其制作成m種型號的零件，全部零件均保持與原材料一樣的厚度，但長度和寬度有所變化，分別為(l1，w1)，(l2，w2)，…，(lm，wm)，其中wi＜li＜L，wi＜W，i=1，2，…，m。m種零件的加工量分別為n1，n2，…，nm。加工時，零件的各邊要分別和原材料的邊相平行；這就是工程上所謂的二維下料問題。尤其當所有型號零件的寬度均與原材料相同，即wi=W，i=1，2，…，m，就是一維下料問題。

對于上述一維單一原材料下料問題，建立相應的數學模型，并同時求解下列問題：在生產能力允許的情況下給出滿足要求的下料方案，然后求出完成相同任務所需的原材料數，并計算廢料總長度和使用的下料方式數和。單一原材料的長度為3 000 mm，現有53種不同長度的零件需要加工。……