The manufacturing sector contributes substantially to environmental degradation through its wastewater emissions. In order to reduce wastewater discharge, we introduce wastewater discharge constraints into the capacitated lot sizing problem (CLSP) and apply the resulting mathematical model to the production process in the electroforming industry. In the electroforming process, we satisfy the customer's demand for different electroforming products in different periods and optimize the overall production expenditure without violating the capacity constraints and wastewater discharge constraints. In order to obtain an optimal solution quickly, we propose an algorithm that combines column generation (CG) with Variable Neighborhood Descent (VND). It generates a relaxed solution through CG and then adjusts this solution to arrive at a solution in integer form. Then, the quality of the solution is enhanced through VND. Experimental results show that in 88% of the cases CG-VND gives a better solution under the same computational resources. Compared to traditional heuristic algorithms, this algorithm produces higher-quality solutions and demonstrates greater application value.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Improved Column Generation Algorithm for the Capacitated Lot Sizing Problem with Wastewater Discharge Limitations

  • Zheng Zhou,
  • Bin Qian,
  • Rong Hu,
  • Nai-kang Yu

摘要

The manufacturing sector contributes substantially to environmental degradation through its wastewater emissions. In order to reduce wastewater discharge, we introduce wastewater discharge constraints into the capacitated lot sizing problem (CLSP) and apply the resulting mathematical model to the production process in the electroforming industry. In the electroforming process, we satisfy the customer's demand for different electroforming products in different periods and optimize the overall production expenditure without violating the capacity constraints and wastewater discharge constraints. In order to obtain an optimal solution quickly, we propose an algorithm that combines column generation (CG) with Variable Neighborhood Descent (VND). It generates a relaxed solution through CG and then adjusts this solution to arrive at a solution in integer form. Then, the quality of the solution is enhanced through VND. Experimental results show that in 88% of the cases CG-VND gives a better solution under the same computational resources. Compared to traditional heuristic algorithms, this algorithm produces higher-quality solutions and demonstrates greater application value.