有区间约束单机延误排序问题

研究一类推广的从准备时间ｒｉ到交工期ｄｉ的多重ｒ／ｄ区间排序问题——有区间约束单机延误排序问题。就该问题的一般情形而言证明了它是ＮＰ—困难的，对问题的特殊情形证明了它是多项式时间可解的。     

具有优先约束的单机随机排序问题

讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法.     

机器排序的几个问题及结果

本文以生产计划中的能力受限单机排序问题、加工过程中产品可以拆分到不同机器上加工的平行机排序问题和基于ＪＩＴ生产哲理的平行机排序问题为主，按能力受限单机排序问题、正则目标函数平行机排序问题变形和非正则目标函数平行机排序问题，介绍它们的模型和最近的几个理论研究结果．同时提出有待研究的问题．     

工件间具有串并有向图约束的单机随机排序问题

研究机器发生随机故障的单机排序问题,其中工件间的优先约束为串并有向图,目标函数为极小化加权完工时间和,证明了此问题多项式时间可解,并给出了多项式时间算法.     

序列错位限制下最小化完工时间和的继列分批重新排序

在单机分批排序中,一个原始工件集已经分好批排好顺序,使得给定的目标函数最小.当一个新的工件集到来时,决策者需要插入这些新工件到原来的顺序中,这样使得原始工件就会产生一些错位.但为了满足对原始工件集的要求而不过分的打乱它们的顺序的条件下,使得新的目标值为最优.本文主要研究的是在序列错位量限制的条件下,继列分批最小化总完工时间的重新排序问题,对于最大序列错位和总序列错位的不同约束情况下,研究可行排序和最优排序的结构性质,进而设计了它们的多项式时间算法.     

两台单机的合作排序问题北大核心CSCD

本文研究下面情形的排序问题,两个代理商联合加工来自客户的一个工件集,每个代理商仅有一台单机用于加工工件,每个工件仅需被其中的一台单机无中断地加工一次.在完成分配工件的加工任务后,每个代理商将获得一定的收益并付出一定的加工费用.需要找出工件集的一个最优划分,使得两个代理商的净收益乘积最大.本文研究三个不同经典排序目标作为加工费用的两机合作排序模型,证明模型复杂性,分析最优解结构并设计动态规划算法.     

最小化提前/延误赋权工件数及时窗惩罚的排序问题

研究赋权提前/延误工件数的公共时窗单机排序问题,时窗的位置和大小待定且由惩罚费用衡量.首先给出最优排序的一些性质,进而提出一个多项式时间算法以最小化这些费用的和.     

一类加工时间依赖资源的单机排序问题

讨论了一类有准备时间且任务的加工时间依赖资源的单机排序问题.目标函数为最大完工时间与分配给各任务资源消耗量的加权线性组合.给出了问题的若干相关性质.在此基础上,对于任务之间无优先约束和有任意优先约束的情况.分别给出了最优排列算法和最优资源分配方法.并用数值例子作了说明.     

MDD函数在单机总误工排序问题中的作用

本文把工件的修正工期（MDD：Modified Due Date）看成工件关于时间的函数，通过研究该函数在一定区间的性质建立了一个具有全局意义的定理，利用这个定理可以方便地导出有关单机总误工排序问题的一些重要结论．这些工作既能够很好地解释常用的MI）D规则的有效性，同时也说明MDD函数可以成为解决单机总误工排序问题的基本工具．     

工件可拒绝排序问题综述

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.     

A tighter bound for FFd algorithm

1. IntroductionIn bin packing, a list L of items, i.e. numbers in the range (0, 1], are to be packed illtobins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The minimal number of bins into which L can be packed is denoted by OPT (L) for the listL. The first~fit-decreasing (FFD) algorithm first sorts the list into a non-increasing orderand then processes the pieces in that order by placing each item into the first bin icao whiChit fits. For tlist L, l…     

Max–min Bin Packing Algorithm and its application in nano-particles filling

With regard to existing bin packing algorithms, higher packing efficiency often leads to lower packing speed while higher packing speed leads to lower packing efficiency. Packing speed and packing efficiency of existing bin packing algorithms including NFD, NF, FF, FFD, BF and BFD correlates negatively with each other, thus resulting in the failure of existing bin packing algorithms to satisfy the demand of nano-particles filling for both high speed and high efficiency. The paper provides a new bin packing algorithm, Max–min Bin Packing Algorithm (MM), which realizes both high packing speed and high packing efficiency. MM has the same packing speed as NFD (whose packing speed ranks no. 1 among existing bin packing algorithms); in case that the size repetition rate of objects to be packed is over 5, MM can realize almost the same packing efficiency as BFD (whose packing efficiency ranks No. 1 among existing bin packing algorithms), and in case that the size repetition rate of objects to be packed is over 500, MM can achieve exactly the same packing efficiency as BFD. With respect to application of nano-particles filling, the size repetition rate of nano particles to be packed is usually in thousands or ten thousands, far higher than 5 or 500. Consequently, in application of nano-particles filling, the packing efficiency of MM is exactly equal to that of BFD. Thus the irreconcilable conflict between packing speed and packing efficiency is successfully removed by MM, which leads to MM having better packing effect than any existing bin packing algorithm. In practice, there are few cases when the size repetition of objects to be packed is lower than 5. Therefore the MM is not necessarily limited to nano-particles filling, and can also be widely used in other applications besides nano-particles filling. Especially, MM has significant value in application of nano-particles filling such as nano printing and nano tooth filling.     

First fit decreasing scheduling on uniform multiprocessors

Independent tasks are nonpreemptively scheduled on m≥2 processors which are assumed to have different speeds. The purpose of this paper is to show that the worst case ratio of the multifit algorithm MF, which is based on the bin-packing method FFD (first fit decreasing), depends on the order of the processors and that the MF has a better worst case behavior than the well-known LPT algorithm for certain processor configurations.     

A new proof for the first-fit decreasing bin-packing algorithm

This paper provides a new proof of a classical result of bin-packing, namely the $\text{11}\text{9}$ performance bound for the first-fit decreasing algorithm. In bin-packing, a list of real numbers in (0,1] is to be packed into a minimal number of bins, each of which holds a total of at most 1. The first-fit decreasing (FFD) algorithm packs each number in order of nonincreasing size into the first bin in which it fits. In his doctoral dissertation, D. S. Johnson (“Near-Optimal Bin Packing Algorithms,” Doctoral thesis, MIT, Cambridge, Mass., 1973) proved that for every list L, $\text{FFD}\text{(L) ?}\text{11}\text{9}\text{OPT}\text{(L) + 4}$, where FFD(L) and OPT(L) denote the number of bins used by FFD and an optimal packing, respectively. Unfortunately, his proof required more than 100 pages! This paper contains a much shorter and simpler proof that $\text{FFD}\text{(L) ?}\text{11}\text{9}\text{OPT}\text{(L) + 3}$.     

A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm

The first fit decreasing (FFD) heuristic algorithm is one of the most famous and most studied methods for an approximative solution of the bin-packing problem. For a listL, let OPT(L) denote the minimal number of bins into whichL can be packed, and let FFD(L) denote the number of bins used by FFD. Johnson^[1] showed that for every listL, FFD(L)11/9OPT(L)+4. His proof required more than 100 pages. Later, Baker^[2] gave a much shorter and simpler proof for FFD(L)11/9 OPT(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 previous ones.In Commemoration of the 15th Anniversary of the Acta Mathematicae Applicatae SinicaThis work was done when the author visited the Forschungsinstitut für Diskrete Mathematik of Universität Bonn during the period from September to December, 1990. Supported by Sonderforshungsbereich 303 (DFG).     

Two-Dimensional Finite Bin-Packing Algorithms

Given a set of rectangular pieces, the two-dimensional bin-packing problem is to place the pieces into an open-ended bin of infinite height such that the height of the resulting packing is minimized. In this paper we analyse the performance of two-dimensional bin-packing heuristics when applied to the special case of packing into finite bins. We develop new bin-packing heuristics by adapting the bottom-left packing method and the next-fit, first-fit and best-fit level-oriented packing heuristics to the finite-bin case. We present our implementation of these algorithms, and compare them to other finite-bin heuristics. Our computational results indicate that the heuristics presented in this paper are suitable for practical use, and behave in a manner which reflects the proven worst-case bounds for the two-dimensional open-ended bin-packing problem.     

A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital

Publicly-funded hospitals are typically allocated an annual budget by the government based on the number of enrollees in the region. Given tight budget constraints, the capacity of resources is fairly fixed. Such hospitals strive to maximize the utilization of their resources through continuous improvement and optimization techniques. We address a surgical case scheduling problem experienced at a publicly-funded hospital and conceptualize this multi-period, multi-resource, priority-based case scheduling problem as an unequal-sized, multi-bin, multi-dimensional dual bin-packing problem. A mixed integer programming model and a heuristic based on the first fit decreasing algorithm are presented. Resource availability, case priorities, and variation in surgery times are key features included in our model. Our proposed approach led to substantial savings, 20% reduction in number of days and up to 20% increase in operating room utilization, when compared to real schedules obtained from the surgical department at a publicly-funded hospital.     

Bin packing: On optimizing the number of pieces packed

We consider bin-packing variations related to the well-studied problem of maximizing the total number of pieces packed into a fixed set of bins. We show that, when the objective is to minimize the total number of pieces packed subject to the constraint that no unpacked piece will fit, no polynomial-time relative approximation algorithm exists (unless, of course,P=NP). That is, we prove that it isNP-hard to guarantee packing no more than a constant multiple of the optimal number of pieces, for any constant. This appears to be the first bin-packing problem for which this property has been demonstrated. Furthermore, this result also holds for the allied packing variant which seeks to minimize the maximum number of pieces packed in any single bin. We find the situation to be markedly better for the problem of maximizing the minimum number of pieces in any bin. If all bins possess the same capacity, we prove that the familiar SPF rule is an absolute approximation algorithm with additive constant 1, and can therefore be regarded as a best possible heuristic. For the more general and difficult case in which bin capacities may differ, it turns out that SPF fails to qualify as even a relative approximation algorithm. However, we devise an implementation of the well-known FFD heuristic, which we show to be a relative approximation algorithm, yielding a worst-case performance ratio of 1/2 with additive constant 0. Moreover, we prove that (unlessP=NP) no polynomial-time algorithm can guarantee a higher ratio without sacrificing the additive constant.This author's research is supported in part by the National Science Foundation under grants ECS-8403859 and MIP-8603879.     

The Container Transshipment Problem: Searching Representation Landscapes with Metaheuristic Algorithms

The container transshipment problem involves scheduling a fleet of lorries to collect and deliver containers of various sizes while minimizing the total distance travelled. The problem originates in the need for logistics companies to solve the problem on a regular basis as part of their daily operations. In this paper, we compare two genetic algorithms tailored to solve this problem based on permutation and bin-packing inspired encodings. Results are presented and analysed in order to evaluate the validity and robustness of the two approaches. As part of the analysis, bounds were calculated to determine how well both GAs perform in absolute terms as well as relative to each other. Of the two GA there is one clear winner, although it is not the one that would have been indicated by previous research. Whilst the winning GA is able to generate significant savings in practice, compared to the optimum there remains room for further improvement.