I have i items and I should pre-packed m knapsacks with identical items where only K<n items can be packed. Also, we should have only one of each item in each sack. The time capacity for knapsacks preparation is limited to Cm for each sack. The ti is the packaging time of item i. The objective is to minimize the packaging costs. I believe it is a multiply constrained knapsack problem and it is also bounded. However, It has some similarities and differences with bin packing problem as well. I am wondering if this problem is a variant of knapsack problem. Is it still NP-hard? If so, how can I prove it? Thanks. The formulation is: \[ \begin{array}{} \min &\sum_{i \in I} c_i z_i x_m &~ &~\\ ~ &\sum_{i \in I} z_i &\le K &~\\ ~ &\sum_{i \in I} t_i x_{m} &\le C_m &\forall ~m \in M\\ ~ &x_m &\le u &\forall ~m \in M\\ ~ &x_m \in \mathbb{Z}_{+} &~ &\forall ~m \in M\\ ~ &z_i \in \{0,1\} &~ &\forall ~i \in I \end{array} \] |

It seems to me that bags should have capacity and items have weights.

What is "the time limit on filling each bag"? Are the bags being filled consecutively or something else? How do you write it as a constraint?

What is the packing cost? Is the time required to pack each item or each tiem value?

Your question seems too vague to get a good answer.

We don't consider weight for bags; however, we can fill the bags in limited the time as much as we can. The time limit on filing the each bags is the time capacity which is restricted to our model. The bags should fill simultaneously and identically as well. The packing cost includes the labor cost and operations costs.

Could you provide a verbal definition of your variables?

\(z_{i}=1\) if the item i is selected

\(x_{m}\) is the number of package for knapsack m

OK, can you specify the sign of the the coefficients \(c_i\), \(t_i\) and \(C_m\)?

It also seems like something is wrong with the objective function. You are only summing over the index set \(I\) but the \(x\)-variable is index by \(m\).