دانلود رایگان مقاله حداقل سازی حداکثر تاخیر در bin packing تک بعدی

abstract

In the One-dimensional Bin Packing problem (1-BP) items of different lengths must be assigned to a minimum number of bins of unit length. Regarding each item as a job that requires unit time and some resource amount, and each bin as the total (discrete) resource available per time unit, the 1-BP objective is the minimization of the makespan Cmax ¼ maxjfCjg. We here generalize the problem to the case in which each item j is due by some date dj: our objective is to minimize a convex combination of Cmax and Lmax ¼ maxjfCj djg. For this problem we propose a time-indexed Mixed Integer Linear Programming formulation. The formulation can be decomposed and solved by column generation relegating single-bin packing to a pricing problem to be solved dynamically. We use bounds to (individual terms of) the objective function to address the oddity of activation constraints. In this way, we get very good gaps for instances that are considered difficult for the 1-BP.

5. Conclusions

We presented and exact ILP formulation and a heuristic algorithm for a 1-dimensional bin packing problem with due dates, where the objective is to minimize a convex combination of the number of bins and the maximum lateness of parts. Cutting/packing problems with due dates are increasingly studied and have important practical applications. One quality of the approach here described is flexibility: in fact, a time-indexed formulation can easily be extended to different scheduling objectives. On the other hand, a typical drawback of this type of formulation is the quite large number of variables and constraints. The crucial role that in our experience lower and upper bounds played to strengthen activation constraints and to fix 0–1 variables suggests that, in future research, an adequate attention is to be paid to bounding effectively the objective function. Other issues, such as the design of an exact Branch-and-Price algorithm, the computation of the Pareto frontier of Cmax vs. Lmax and the extension of the bound strengthening technique to different scheduling objective functions deserve further investigation. Finally, future generalizations of the approach to the s-dimensional problem can take advantage from the decomposition here described.