带时间效率约束的一维装箱问题

One-Dimensional Packing Problem with Time Efficiency Constraint

摘要: 一维装箱问题是指把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。本文研究了带时间效率约束的一维装箱问题，时间效率约束为不同机器的装箱效率不同，目标是装箱数目近似比与装箱时间近似比的乘积最小。本文给出了一种求解带时间效率约束的一维装箱问题的近似算法，分析了问题的NP-困难性，并证明出目标近似比的乘积为 (其中)。 One dimensional packing problem is to put a certain number of items into some boxes with the same capacity, so that the sum of the sizes of the items in each box does not exceed the box capacity and minimize the number of boxes used. In this paper, we study one-dimensional packing problem with time efficiency constraint. The time efficiency constraint is that different machines have dif-ferent packing efficiency. The aim is to minimize the product of the approximate ratio of the num-ber of packing and the approximate ratio of the time of packing. We present an approximation algo-rithm for the problem and analyze the NP-Hardness. We prove that the algorithm has the approxi-mation ratio is .

1. 引言

一维装箱问题是指把一定数量的物品放入容量相同的一些箱子中，使得每个箱子中的物品大小之和不超过箱子容量并使所用的箱子数目最少。一维装箱问题是组合优化问题中最基本的一类NP-hard问题 [1]，在20世纪70年代就引起了广泛的谈论与研究，并有了显著的成果 [2] [3] [4]。然而随着社会的发展，研究者们对经典装箱算法的研究已经较为成熟，想要进一步突破经典装箱的求解算法难度很大。因此，研究者们开始研究与现代化实际应用相结合的带约束的装箱问题 [5] [6] [7] [8]。

在当今社会上，装箱问题往往与装箱时间相联系，例如：物流运输既需要使用车辆的数目较少，也需要装车时间较短。而装箱时间与装箱机器的速度有关，由于机器的老化会导致装箱的速度不同，从而导致不同机器装同一个物体的时间有差异。因此，本文考虑了一种新的时间约束类型的装箱问题即带时间效率约束的一维装箱问题，分析了问题的NP困难性，给出了一种求解带时间效率约束的一维装箱问题的近似算法，并证明出目标近似比的乘积为 $\left(2+c\right)\left(2-\frac{1}{m}\right)$ (其中 $0<c\le 1$ )。

2. 相关知识

一维装箱问题是给定n个物品序列 $L=\left(a_1,a_2,\cdots ,a_n\right)$，每个物品 $a_i$ 的尺寸为 $s\left(a_i\right)\in \left(0,1\right]$， $i=1,2,\cdots ,n$，要求把这些物品装入若干个单位容量箱子中，目标是使得所使用的箱子数目达到最少。

对于一个装箱问题，L是问题的任意输入物品序列，设A是求解装箱问题的一个近似算法，算法A返回的解的目标值为 $A\left(L\right)$，序列L对应最优解的目标值为 $A^{\ast }\left(L\right)$，则算法的近似比定义为

$R_A\left(L\right)=\frac{A\left(L\right)}{A^{\ast }\left(L\right)}$。

求解一维装箱问题的近似算法有很多 [9] [10] [11]，其中下次适应算法(Next Fit Algorithm，简称为NF算法)是最简单也是最早研究的一个算法，其策略为：按照物品给定的顺序装箱时，始终保持只打开一个箱子，对于当前要装入的物品，检查是否能装入当前打开的箱子，若不能，则关闭该箱子打开一个空箱子装该物品。NF算法的时间复杂度为 $O\left(n\right)$，最坏情况渐近性能比为2。

3. 问题描述

经典一维装箱问题的目标是使用单位箱子数目最少，但此模型过于单一。该问题的数学模型为

$\begin{array}{l}\min z\left(y\right)={\displaystyle \underset{j=1}{\overset{m}{\sum }}{y}_j}\\ \text{s}\text{.t}.{\displaystyle \underset{i=1}{\overset{n}{\sum }}{w}_i{x}_{ij}}\le W{y}_j\text{,}\left(j=1,2,\cdots ,m\right)(3.1)\\ {\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ij}}=1\text{,}\left(j=1,2,\cdots ,m\right)(3.2)\\ x_{ij}=0或1,\left(i=1,2,\cdots ,n,j=1,2,\cdots ,m\right)(3.3)\\ y_j=0或1,\left(i=1,2,\cdots ,m\right)(\; 3.4\; )\end{array}$

其中目标函数为使用箱子数目；公式(3.1)表示物品装入箱子的总容量(或总体积)不能超过箱子的容量(或体积)；公式(3.2)表示每个物品只能装入一个箱子；公式(3.3)中，当 $x_{ij}=1$ 时表示物品i被装入箱子j中，当 $x_{ij}=0$ 时表示物品i未被装入箱子j中；公式(3.4)中，当 $y_j=1$ 时第j个箱子被使用，当 $y_j=0$ 时第j个箱子未被使用。

本文考虑的装箱问题加上了时间效率约束，同时考虑装箱数目和时间，在数目上，要求装箱数目最少；在时间上，要求装箱时间最少。为了确保达同时到两个目标，本文采用了一种新的目标设定方法，即目标是装箱数目近似比与装箱时间近似比的乘积最小。与传统的解决多目标问题的方法比较，这种目标设定方法合理地避免了多目标规划问题求解过程中可能出现的达到一级目标但达不到二级目标的结果。

效率约束是指，当使用不同机器装箱时，由于机器的老化程度不同，每个机器的装箱速度不同，不妨设装箱速度最快的机器的效率为1，且效率低于0.5时机器需要维修。装箱时间与机器效率成反比，例如使用效率为1的机器将n个物体装箱的时间为 $\left\{t_1,t_2,\cdots ,t_n\right\}$，那么使用效率为0.6的机器将n个物体装箱的时间为 $\left\{\frac{5t_1}{3},\frac{5t_2}{3},\cdots ,\frac{5t_n}{3}\right\}$。

带效率约束的一维装箱问题描述如下：给定n个物品序列 $L=\left(a_1,a_2,\cdots ,a_n\right)$，每个物品 $a_i$ 的尺寸为 $s\left(a_i\right)\in \left(0,1\right]$， $i=1,2,\cdots ,n$，让m个正常使用的机器同时装箱，机器效率 ${\alpha }_j\in \left[0.5,1\right]$， $j=1,2,\cdots ,m$，使用效率为1的机器将n个物体装箱的时间为 $\left\{t_1,t_2,\cdots ,t_n\right\}$，要求把所有物品装入若干个单位容量的箱子中。目标是装箱数目近似比与装箱时间近似比的乘积最小。

4. 研究内容

4.1. 数学模型

$\begin{array}{l}\min R_{A_T}\left(L\right)\times R_A\left(L\right)\\ \text{s}\text{.t}\text{.}A\left(L\right)={\displaystyle \underset{r=1}{\overset{s}{\sum }}{y}_r}(4.1)\\ A_T\left(L\right)={\max }_{1\le j\le m}{\displaystyle \underset{r=1}{\overset{s}{\sum }}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ir}{\delta }_{ij}}}\frac{t_i}{{\alpha }_j}{y}_r(4.2)\\ R_A\left(L\right)=\frac{A\left(L\right)}{A^{\ast }\left(L\right)}(\; 4.3\; )\end{array}$

$\begin{array}{l}{R}_{A_T}\left(L\right)=\frac{A_T\left(L\right)}{A_T^{\ast }\left(L\right)}(4.4)\\ {\displaystyle \underset{i=1}{\overset{n}{\sum }}s}\left(a_i\right)x_{ir}\le W{y}_{r}r=1,\cdots ,s(4.5)\\ {\displaystyle \underset{i=1}{\overset{n}{\sum }}{x}_{ir}}=1r=1,\cdots ,s(4.6)\\ {\displaystyle \underset{i=1}{\overset{n}{\sum }}{\delta }_{ij}}=1j=1,\cdots ,m(\; 4.7\; )\end{array}$

$\begin{array}{l}{x}_{ir}=0或1i=1,\cdots ,n;r=1,\cdots ,s(4.8)\\ {\delta }_{ij}=0或1j=1,\cdots ,m;i=1,\cdots ,n(4.9)\\ y_r=0或1r=1,\cdots ,s(4.10)\\ {\gamma }_j=1j=1,\cdots ,m(\; 4.11\; )\end{array}$

其中：(4.1)表示用算法A装箱使用的箱子数目；(4.2)表示m个机器中装箱时间最长的机器所花费的时间；(4.3)表示算法A装箱数目近似比；(4.4)表示算法A装箱时间近似比；(4.5)表示物体总量不超过箱子容量；W = 1表示箱子容量；(4.6)表示每一个物体只能装入一个箱子；(4.7)表示每一个物体只能分配给一个机器；(4.8)中 $x_{ir}=1$ 表示第i个物品装入第r个箱子，反之表示第i个物品未装入第r个箱子；(4.9)中 ${\delta }_{ij}=1$ 表示第i个物品分配给第j个机器，反之表示第i个物品未分配给第j个机器；(4.10)中 $y_r=1$ 表示第r个箱子被使用，反之表示第r个箱子未被使用；(4.11)表示所有机器都被使用。

4.2. 算法设计

算法A

Input：物品序列 $L=\left(a_1,a_2,\cdots ,a_n\right)$ 以及每个物品 $a_i$ 的尺寸为 $s\left(a_i\right)\in \left(0,1\right]$， $i=1,2,\cdots ,n$，机器效率 ${\alpha }_j\in \left[0.5,1\right]$， $j=1,2,\cdots ,m$，使用效率为1的机器将n个物体装箱的时间为 $\left\{t_1,t_2,\cdots ,t_n\right\}$。

Output：使用的箱子数及装箱方案。

Begin

Step 1：将物体按照装箱时间从大到小排序 $t_1\ge t_2\ge \cdots \ge t_n$，如果装箱时间相同，那么按照物品尺寸排序。

Step 2：将机器效率按照从大到小排序 ${\alpha }_1\ge {\alpha }_2\ge \cdots \ge {\alpha }_m$，其中 ${\alpha }_1=1$， ${\alpha }_j\in \left[0.5,1\right],j=2,3,\cdots ,m$。

Step 3：若 $n=km$，则n不变；若 $\left(k-1\right)m<n<km$ (k为任意整数)，则 $n=km$，且 $t_{n+1}=t_{n+2}=\cdots =t_{km}=0$。

Step 4：若k为偶数，记物体集合为

$S_j=\left\{a_j,a_{2m-j+1},a_{2m+j},a_{4m-j+1},a_{4m+j},\cdots ,a_{km-j+1}\right\},j=1,2,\cdots ,m$，

其对应的装箱时间集合为

$T_j=\left\{t_j,t_{2m-j+1},t_{2m+j},t_{4m-j+1},t_{4m+j},\cdots ,t_{km-j+1}\right\},j=1,2,\cdots ,m$。

若k为奇数，记物体集合为

$S_j=\left\{a_j,a_{2m-j+1},a_{2m+j},a_{4m-j+1},a_{4m+j},\cdots ,a_{\left(k-1\right)m+j}\right\},j=1,2,\cdots ,m$，

其对应的装箱时间集合为

$T_j=\left\{t_j,t_{2m-j+1},t_{2m+j},t_{4m-j+1},t_{4m+j},\cdots ,t_{\left(k-1\right)m+j}\right\},j=1,2,\cdots ,m$。

那么每个机器所需装箱物体的个数为k个。

Step 5：令 $l\left(T_j\right)$ 表示 $T_j$ 中元素相加的总和，将 $l\left(T_j\right)$ 从大到小重新排序，设为 $l\left(T_1\right)\ge l\left(T_2\right)\ge \cdots \ge l\left(T_m\right)$，将第j个子集 $S_j$ 中所有元素分配给机器 $m_j\left(j=1,2,\cdots ,m\right)$，其效率为 ${\alpha }_j$。分配后的第j台机器所花费的总时间用 $l\left(m_j\right)$ 表示，即 $l\left(m_j\right)=\frac{l\left(T_j\right)}{{\alpha }_j}$。

Step 6：对于第j台机器：

$\begin{array}{l}令B=\varnothing ,s_0=0,r_j=1,B_{S_j,r_j}:=B\cup \left\{a_1\right\},s\left(B_{S_j,r_j}\right):=s_0+s\left(a_1\right)\\ \text{For}c=2\text{to}k\text{do}\\ \text{If}s\left(a_c\right)+s\left(B_{S_j,r_j}\right)\le 1\text{then}\\ 置B_{S_j,r_j}:=B_{S_j,r_j}\cup \left\{a_c\right\},s\left(B_{S_j,r_j}\right):=s\left(B_{S_j,r_j}\right)+s\left(a_c\right)\\ \text{Else}\\ r_j:=r_j+1,B_{S_j,r_j}:=B\cup \left\{a_c\right\},s\left(B_{S_j,r_j}\right):=s_0+s(\; a\; c\; )\end{array}$

令装箱总数 $h=r_1+r_2+\cdots +r_j$。

Step 7：输出箱子数目h和装箱方案 $B_{S_1,1},B_{S_1,2},\cdots ,B_{S_1,r_1},\cdots ,B_{S_j,1},B_{S_j,2},\cdots ,B_{S_j,r_j}$。

End

4.3. 算法分析

引理1：对任意的 $k\ge 2$，对任意实例I，有 $R_{A_T}\left(I\right)=2-\frac{1}{m}$。

证明：设

$l\left(m_a\right)=\max \left(l\left(m_j\right)\right),j=1,2,\cdots ,m;l\left(m_b\right)=\min \left(l\left(m_j\right)\right),j=1,2,\cdots ,m$，

则有 $A_T\left(I\right)=l\left(m_a\right)$。设机器 $m_a$ 所需装箱的元素集合为 $S_a$，对应装箱时间为 $T_a$，机器 $m_b$ 的元素集合为 $S_b$，对应装箱时间为 $T_b$。因此 $l\left(m_a\right)-l\left(m_b\right)=\frac{l\left(T_a\right)}{{\alpha }_a}-\frac{l\left(T_b\right)}{{\alpha }_b}$。

下面讨论 $l\left(m_a\right)-l\left(m_b\right)$ 的大小。

当 $A_T^{\ast }\left(I\right)\ge 2t_1$ 时，令

$\begin{array}{l}{\alpha }_c=\max \left\{{\alpha }_a,{\alpha }_b\right\},l\left(T_c\right)=\max \left\{l\left(T_a\right),l\left(T_b\right)\right\},\\ {\alpha }_d=\min \left\{{\alpha }_a,{\alpha }_b\right\},l\left(T_d\right)=\min \left\{l\left(T_a\right),l\left(T_b\right)\right\},\end{array}$

那么

$\begin{array}{c}l\left(m_a\right)-l\left(m_b\right)=\frac{l\left(T_a\right)}{{\alpha }_a}-\frac{l\left(T_b\right)}{{\alpha }_b}=\frac{{\alpha }_{b}l\left(T_a\right)-{\alpha }_{a}l\left(T_b\right)}{{\alpha }_a{\alpha }_b}\\ \le \frac{{\alpha }_c\left|l\left(T_a\right)-l\left(T_b\right)\right|}{{\alpha }_a{\alpha }_b}=\frac{{\alpha }_c\left(l\left(T_c\right)-l\left(T_d\right)\right)}{{\alpha }_a{\alpha }_b}\end{array}$

为了方便计算，不妨设 $T=\left(t_{i1},t_{i2},t_{i3},\cdots ,t_{ik}\right),i=1,2,\cdots ,m$。

那么

$\begin{array}{c}l\left(m_a\right)-l\left(m_b\right)\le \frac{{\alpha }_c\left(l\left(T_c\right)-l\left(T_d\right)\right)}{{\alpha }_a{\alpha }_b}\\ =\frac{{\alpha }_c}{{\alpha }_a{\alpha }_b}\left[\left(t_{c1}+t_{c2}+t_{c3}+\cdots +t_{ck}\right)-\left(t_{d1}+t_{d2}+t_{d3}+\cdots +t_{dk}\right)\right]\\ =\frac{{\alpha }_c}{{\alpha }_a{\alpha }_b}\left[t_{c1}-\left(t_{d1}-t_{c2}\right)-\left(t_{d2}-t_{c3}\right)-\cdots -\left(t_{d\left(k-1\right)}-t_{ck}\right)-t_{dk}\right]\\ \le \frac{{\alpha }_c}{{\alpha }_a{\alpha }_b}\left(t_{c1}-t_{dk}\right)\le \frac{{\alpha }_c}{{\alpha }_a{\alpha }_b}{t}_{c1}\le 2t_1\end{array}$

这时，我们有 $A_T^{\ast }\left(I\right)\ge 2t_1\ge l\left(m_a\right)-l\left(m_b\right)$。

当 $A_T^{\ast }\left(I\right)<2t_1$ 时，若 ${\alpha }_a>{\alpha }_b$，由算法可知， $l\left(T_a\right)>l\left(T_b\right)$。就有

$\begin{array}{c}l\left(m_a\right)-l\left(m_b\right)-\frac{t_{a1}}{{\alpha }_a}=\frac{l\left(T_a\right)}{{\alpha }_a}-\frac{l\left(T_b\right)}{{\alpha }_b}-\frac{t_{a1}}{{\alpha }_a}\\ =\frac{{\alpha }_b\left(t_{a2}+t_{a3}+t_{a4}+\cdots +t_{ak}\right)-{\alpha }_a\left(t_{b1}+t_{b2}+t_{b3}+\cdots +t_{bk}\right)}{{\alpha }_a{\alpha }_b}\\ \le \frac{{\alpha }_a}{{\alpha }_a{\alpha }_b}\left[\left(t_{a2}+t_{a3}+t_{a4}+\cdots +t_{ak}\right)-\left(t_{b1}+t_{b2}+t_{b3}+\cdots +t_{bk}\right)\right]\\ =\frac{1}{{\alpha }_b}\left[\left(t_{a2}-t_{b1}\right)+\left(t_{a3}-t_{b2}\right)+\cdots +\left(t_{ak}-t_{b\left(k-1\right)}\right)-t_{bk}\right]\le 0\end{array}$

即 $l\left(m_a\right)-l\left(m_b\right)\le \frac{t_{a1}}{{\alpha }_a}$。而 $A_T^{\ast }\left(I\right)\ge \frac{t_{a1}}{{\alpha }_a}$，故有 $A_T^{\ast }\left(I\right)\ge \frac{t_{a1}}{{\alpha }_a}\ge l\left(m_a\right)-l\left(m_b\right)$。

若 ${\alpha }_a\le {\alpha }_b$，由算法可知 $l\left(T_a\right)\le l\left(T_b\right)$，且有 $l\left(m_a\right)\ge l\left(m_b\right)$，即 $\frac{l\left(T_a\right)}{{\alpha }_a}\ge \frac{l\left(T_b\right)}{{\alpha }_b}$。此时有 $l\left(T_a\right)\le l\left(T_b\right)\le \frac{{\alpha }_b}{{\alpha }_a}l\left(T_a\right)$。当 $t_1$ 确定时，这种情况是可数的，并且在这种情况下， $l\left(m_a\right)-l\left(m_b\right)$ 的极限情

况是当 ${\alpha }_a=0.5,{\alpha }_b=1,l\left(T_a\right)=l\left(T_b\right)$ 时。

那么此时有

$l\left(m_a\right)-l\left(m_b\right)=2l\left(T_a\right)-l\left(T_b\right)=2l\left(T_a\right)-l\left(T_a\right)=l(\; T\; a\; )$

而

$A_T^{\ast }\ge l\left(m_b\right)+\frac{l\left(m_a\right)-l\left(m_b\right)}{m}=l\left(T_b\right)+\frac{2l\left(T_a\right)-l\left(T_b\right)}{m}\ge l\left(T_a\right)=l\left(m_a\right)-l\left(m_b\right)$。

故当 ${\alpha }_a\le {\alpha }_b$ 时， $A_T^{\ast }\left(I\right)\ge l\left(m_a\right)-l\left(m_b\right)$。

综上我们有 $A_T^{\ast }\left(I\right)\ge l\left(m_a\right)-l\left(m_b\right)$，那么就有

$\begin{array}{c}{A}_T\left(I\right)-A_T^{\ast }\left(I\right)=l\left(m_a\right)-A_T^{\ast }\left(I\right)\le l\left(m_a\right)-\left(l\left(m_b\right)+\frac{l\left(m_a\right)-l\left(m_b\right)}{m}\right)\\ =\left(1-\frac{1}{m}\right)\left(l\left(m_a\right)-l\left(m_b\right)\right)\le \left(1-\frac{1}{m}\right)A_T^{\ast }(\; I\; )\end{array}$

从而有 $A_T\left(I\right)\le \left(2-\frac{1}{m}\right)A_T^{\ast }\left(I\right)$。得证。

引理2：对任意实例I，有 $R_A\left(I\right)=2+c$ (其中 $0<c\le 1$ )。

证明：由算法可知，第j台机器所需装箱的元素集合为 $S_j$，假设使用算法将 $S_j$ 装完需要 ${\beta }_j$ 个箱子，那么将 $S_j$ 中的所需箱子两两结合相加得到 $S_j$ 中所有元素大小之和 $s\left(S_j\right)\ge \frac{\left({\beta }_j-1\right)}{2}$，对 $s\left(S_j\right)$ 求和，就可以得到

$s\left(I\right)={\displaystyle \underset{j=1}{\overset{m}{\sum }}s\left(S_j\right)}\ge \frac{{\displaystyle \underset{j=1}{\overset{m}{\sum }}{\beta }_j}-m}{2}$

又因为 $A\left(I\right)={\displaystyle \underset{j=1}{\overset{m}{\sum }}{\beta }_j}$， $A^{\ast }\left(I\right)\ge s\left(I\right)$，那么有 $\frac{A\left(I\right)}{A^{\ast }\left(I\right)}\le 2+\frac{m}{A^{\ast }\left(I\right)}$，而 $A^{\ast }\left(I\right)$ 表示使用m个机器同时装箱对应的最优解，那么就有 $A^{\ast }\left(I\right)\ge m$。令 $c=\frac{m}{A^{\ast }\left(I\right)}$，那么 $0<c\le 1$，则有 $\frac{A\left(I\right)}{A^{\ast }\left(I\right)}\le 2+c\left(0<c\le 1\right)$。得证。

定理1：装箱时间近似比与装箱数目近似比的乘积是 $\left(2+c\right)\left(2-\frac{1}{m}\right)$ (其中 $0<c\le 1$ )。

证明：由定理1和定理2可知装箱时间近似比为 $2-\frac{1}{m}$，箱子数目的近似比为( $2+c$ ) ( $0<c\le 1$ )，故装箱时间近似比与装箱数目近似比的乘积是 $\left(2+c\right)\left(2-\frac{1}{m}\right)$ (其中 $0<c\le 1$ )。

定理2：算法A的时间复杂度为 $O\left(n\log n\right)$。

证明：算法中的step 1的时间复杂度为 $O\left(n\log n\right)$，step 2和step 5的时间复杂度为 $O\left(m\log m\right)$，step 6的时间复杂度为 $O\left(n\right)$，所以算法A的时间按复杂度为 $O\left(n\log n\right)$。

4.4. 算法应用

下面给一个算法的应用实例。给定物品序列 $L=\left(a_1,a_2,\cdots ,a_{10}\right)$，其尺寸为 $s\left(a_i\right)=\left\{0.4,0.2,0.7,0.3,0.5,0.4,0.2,0.3,0.6,0.2\right\}$， $i=1,2,\cdots ,n$，两台机器同时装箱，装箱效率为 ${\alpha }_j=\left\{1,0.8\right\}$， $j=1,2$，使用效率为1的机器将n个物体装箱的时间为 $T=\left\{2,1,3,2,2,1,1,3,2,1\right\}$。

那么使用算法A装箱的结果为 $A_T\left(L\right)=\frac{45}{4}$， $A\left(L\right)=5$，而 $A_T^{\ast }\left(L\right)=10$， $A^{\ast }\left(L\right)=4$，故满足算法证明结果。

5. 小结

本文提出了一种带时间效率约束的一类一维装箱问题，在传统一维装箱的基础上加了时间效率约束，同时考虑装箱数目和装箱时间，设计算法求出近似比，分析其时间复杂度，并取得了较好的结果。

此外，当物品数目较少且机器数目较多时，该算法的性能较差，本文进一步的工作是根据物品数目的多少来选择不同数量的机器装箱，以达到省时省力的最佳效果。我们未来的工作将继续研究此类问题，以期能对实际生活提供帮助。

致谢

非常感谢对本稿提出意见的审稿人及导师。

基金项目

云南民族大学数学与计算机科学学院研究生项目(SJXY-2021-025)。