Given a list of items and a sequence of variable-sized bins arriving one by one, it is NP-hard to pack the items into the bin list with a goal to minimize the total size of bins from the earliest one to the last used....Given a list of items and a sequence of variable-sized bins arriving one by one, it is NP-hard to pack the items into the bin list with a goal to minimize the total size of bins from the earliest one to the last used. In this paper a set of approximation algorithms is presented for cases in which the ability to preview at most k（〉=2） arriving bins is given. With the essential assumption that all bin sizes are not less than the largest item size, analytical results show the asymptotic worst case ratios of all k-bounded space and offiine algorithms are 2. Based on experiments by applying algorithms to instances in which item sizes and bin sizes are drawn independently from the continuous uniform distribution respectively in the interval [0,u] and [u,l ], averagecase experimental results show that, with fixed k, algorithms with the Best Fit packing（closing） rule are statistically better than those with the First Fit packing（closing） rule.展开更多
In this paper,the berth scheduling problem is transformed into a special two-dimensional packing problem with some constraints.A nonlinear programming model for the problem is established,and a heuristic algorithm is ...In this paper,the berth scheduling problem is transformed into a special two-dimensional packing problem with some constraints.A nonlinear programming model for the problem is established,and a heuristic algorithm is proposed to solve the model.Simulation results show that the algorithm can improve the utilization of berths on discrete berth scheduling in the container port.展开更多
Traditional scheduling algorithms for avionics communication have the shortcoming of messages accumulation,the efficiency and reliability of the service can be improved by combining the distributed integrated modular ...Traditional scheduling algorithms for avionics communication have the shortcoming of messages accumulation,the efficiency and reliability of the service can be improved by combining the distributed integrated modular avionics(DIMA)system with a time trigger mechanism.To further improve the utilization of system resources,the static scheduling algorithm of time triggered service is studied.By making the time trigger message schedule dispersedly,the stabilities of both the available time slots for the event triggered messages and the system will be improved.An improved two-dimensional bin packing algorithm is also presented to achieve the above-mentioned purpose with an extra benefit of better delay performance.展开更多
It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling proble...It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.展开更多
A version of the k-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive a...A version of the k-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive an algorithm with worst-case performance bound 1.7 for k≥3.展开更多
文摘Given a list of items and a sequence of variable-sized bins arriving one by one, it is NP-hard to pack the items into the bin list with a goal to minimize the total size of bins from the earliest one to the last used. In this paper a set of approximation algorithms is presented for cases in which the ability to preview at most k（〉=2） arriving bins is given. With the essential assumption that all bin sizes are not less than the largest item size, analytical results show the asymptotic worst case ratios of all k-bounded space and offiine algorithms are 2. Based on experiments by applying algorithms to instances in which item sizes and bin sizes are drawn independently from the continuous uniform distribution respectively in the interval [0,u] and [u,l ], averagecase experimental results show that, with fixed k, algorithms with the Best Fit packing（closing） rule are statistically better than those with the First Fit packing（closing） rule.
文摘In this paper,the berth scheduling problem is transformed into a special two-dimensional packing problem with some constraints.A nonlinear programming model for the problem is established,and a heuristic algorithm is proposed to solve the model.Simulation results show that the algorithm can improve the utilization of berths on discrete berth scheduling in the container port.
基金Supported by Joint Fundation for Equipment Pre-research of Aerospace Science and Technology
文摘Traditional scheduling algorithms for avionics communication have the shortcoming of messages accumulation,the efficiency and reliability of the service can be improved by combining the distributed integrated modular avionics(DIMA)system with a time trigger mechanism.To further improve the utilization of system resources,the static scheduling algorithm of time triggered service is studied.By making the time trigger message schedule dispersedly,the stabilities of both the available time slots for the event triggered messages and the system will be improved.An improved two-dimensional bin packing algorithm is also presented to achieve the above-mentioned purpose with an extra benefit of better delay performance.
文摘It is a NP-hard problem to schedule a list of nonresumable jobs to the available intervals of an availability-constrained single machine to minimize the scheduling length. This paper transformed this scheduling problem into a variant of the variable-sized bin packing problem, put forward eight bin packing algorithms adapted from the classic one-dimensional bin packing problem and investigated their performances from both of the worst-case and the average-case scenarios. Analytical results show that the worst-case performance ratios of the algorithms are not less than 2. Experimental results for average cases show that the Best Fit and the Best Fit Decreasing algorithm outperform any others for independent and precedence-constrained jobs respectively.
文摘A version of the k-bounded space on-line bin packing problem, where a fixed collection of bin sizes is allowed, is considered. By packing large items into appropriate bins and closing appropriate bins, we can derive an algorithm with worst-case performance bound 1.7 for k≥3.
