In a general case, container ship serves many different ports on each voyage. A stowage planning for container ship made at one port must take account of the influence on subsequent ports. So the complexity of stowage...In a general case, container ship serves many different ports on each voyage. A stowage planning for container ship made at one port must take account of the influence on subsequent ports. So the complexity of stowage planning problem increases due to its multi-ports nature. This problem is NP-hard problem. In order to reduce the computational complexity, the problem is decomposed into two sub-problems in this paper. First, container ship stowage problem (CSSP) is regarded as 'packing problem', ship-bays on the board of vessel are regarded as bins, the number of slots at each bay are taken as capacities of bins, and containers with different characteristics (homogeneous containers group) are treated as items packed. At this stage, there are two objective functions, one is to minimize the number of bays packed by containers and the other is to minimize the number of overstows. Secondly, containers assigned to each bays at first stage are allocate to special slot, the objective functions are to minimize the metacentric height, heel and overstows.The taboo search heuristics algorithm are used to solve the subproblem. The main focus of this paper is on the first subproblem. A case certifies the feasibility of the model and algorithm.展开更多
The first fit decreasing (FFD) heuristic algorithm is one of the most famous and moststudied methods for an approximative solution of the bin-packing problem. For a list L, letOPT(L) denote the minimal number of bins ...The first fit decreasing (FFD) heuristic algorithm is one of the most famous and moststudied methods for an approximative solution of the bin-packing problem. For a list L, letOPT(L) denote the minimal number of bins into which L can be packed, and let FFD(L)denote the number of bins used by FFD. Johnson showed that for every list L, FFD(L)≤11/9OPT(L)+4. His proof required more than 100 pages. Later, Baker gave a much shorterand simpler proof for FFD(L)≤11/9OPT(L)+3. His proof required 22 pages. In this paper,we give a proof for FFD(L)≤11/9 OPT(L)+1. The proof is much simpler than the previousones.展开更多
According to the compound packing problem in ammunition supply system in our army, the non-standard pallet series design model is proposed, and the original problem that can be solved as a set cover problem with a nes...According to the compound packing problem in ammunition supply system in our army, the non-standard pallet series design model is proposed, and the original problem that can be solved as a set cover problem with a nested bin-packing problem, is analyzed, then two heuristic algorithms are applied to solve the problem.展开更多
THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the...THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the item and its size as well, we are to pack all the items in-to bins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The first-fit-decreasing （FFD） algorithm is a famous approximate algorithm for the bin-pack-ing problem. The FFD algorithm first sorts all the list into non-increasing order and then pro-cesses the pieces in that order by placing each item into the first bin into which it fits.展开更多
In 1985, Johnson and Garey[4] devised an algorithm which they call MFFD. Compared with other modifications of the famous FFD algorithm, theirs is apparently simpler in practical applications and substantially improves...In 1985, Johnson and Garey[4] devised an algorithm which they call MFFD. Compared with other modifications of the famous FFD algorithm, theirs is apparently simpler in practical applications and substantially improves the worst case behavior of FFD. In fact, they proved that the inequality MFFD(L) OPT(L)+ holds for all the lists L. Their proof requires 40 pages.In this paper we give a proof for the inequality MFFD(L) OPT(L)+1, L. The proof is much simpler than theirs.展开更多
基金Supported by a Special Fund Support Item of Doctor Subject of Colleges and Universities (No. 2000014125)
文摘In a general case, container ship serves many different ports on each voyage. A stowage planning for container ship made at one port must take account of the influence on subsequent ports. So the complexity of stowage planning problem increases due to its multi-ports nature. This problem is NP-hard problem. In order to reduce the computational complexity, the problem is decomposed into two sub-problems in this paper. First, container ship stowage problem (CSSP) is regarded as 'packing problem', ship-bays on the board of vessel are regarded as bins, the number of slots at each bay are taken as capacities of bins, and containers with different characteristics (homogeneous containers group) are treated as items packed. At this stage, there are two objective functions, one is to minimize the number of bays packed by containers and the other is to minimize the number of overstows. Secondly, containers assigned to each bays at first stage are allocate to special slot, the objective functions are to minimize the metacentric height, heel and overstows.The taboo search heuristics algorithm are used to solve the subproblem. The main focus of this paper is on the first subproblem. A case certifies the feasibility of the model and algorithm.
文摘The first fit decreasing (FFD) heuristic algorithm is one of the most famous and moststudied methods for an approximative solution of the bin-packing problem. For a list L, letOPT(L) denote the minimal number of bins into which L can be packed, and let FFD(L)denote the number of bins used by FFD. Johnson showed that for every list L, FFD(L)≤11/9OPT(L)+4. His proof required more than 100 pages. Later, Baker gave a much shorterand simpler proof for FFD(L)≤11/9OPT(L)+3. His proof required 22 pages. In this paper,we give a proof for FFD(L)≤11/9 OPT(L)+1. The proof is much simpler than the previousones.
文摘According to the compound packing problem in ammunition supply system in our army, the non-standard pallet series design model is proposed, and the original problem that can be solved as a set cover problem with a nested bin-packing problem, is analyzed, then two heuristic algorithms are applied to solve the problem.
文摘THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the item and its size as well, we are to pack all the items in-to bins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The first-fit-decreasing （FFD） algorithm is a famous approximate algorithm for the bin-pack-ing problem. The FFD algorithm first sorts all the list into non-increasing order and then pro-cesses the pieces in that order by placing each item into the first bin into which it fits.
文摘In 1985, Johnson and Garey[4] devised an algorithm which they call MFFD. Compared with other modifications of the famous FFD algorithm, theirs is apparently simpler in practical applications and substantially improves the worst case behavior of FFD. In fact, they proved that the inequality MFFD(L) OPT(L)+ holds for all the lists L. Their proof requires 40 pages.In this paper we give a proof for the inequality MFFD(L) OPT(L)+1, L. The proof is much simpler than theirs.
