凹二次规划问题的一个融合割平面方法的分支定界混合算法

把割平面方法融于分支定界方法之中,本文提出了求解凹二次规划问题的一个融合割平面方法的分支定界混合算法,证明了该算法是收敛的.数值例子也表明这个算法是有效的,并且好于单纯形分支定界算法。     

越库物流调度问题及其近似与精确算法

在提出问题基础上,建立了基于在制品优化目标的调度模型;根据模型的不同调度特征,给出问题求解的启发式近似算法,并对算法的计算复杂性进行分析,提出问题精确求解的分枝定界算法;通过数值实验验证所给出算法的有效性.表明:分枝定界算法可以有效求解多达40个货物品种的准时制配送问题;启发式算法也具有较高的计算精度,为实际越库物流管理奠定算法基础.     

一类带有常系数线性乘积规划问题的分支定界缩减方法

本文给出了一种求解带有常系数线性乘积规划问题的分支定界缩减算法.我们首先利用两个变量乘积的凸包络技术,分别得到目标函数与约束函数中乘积的上界与下界估计,由此构造出原问题的一个松弛凸规划问题.在此基础之上,借助超矩形的缩减技术,提出了确定原问题全局最优值下界的分支定界缩减算法,并从理论上分析了算法的收敛性.最后,利用数值实验验证了算法的有效性与可行性.     

空箱资源约束调度的列生成算法研究

研究了可重用空箱资源约束下的入厂物流车辆运输调度问题。首先对该问题进行数学描述,建立混合整数线性规划模型。鉴于问题的NP难解性,研究求解该问题的列生成方法,提出虚工件等技巧,建立适合序列依赖的可重用资源约束调度的列生成主问题模型以及基于检验数求解的子问题模型,并研究求解子问题的动态规划算法。进一步采用分支定界技巧,最终提出适合本问题求解的列生成算法。数值实验表明方法的有效性与高效性。     

基于分支定价算法的多时间窗家庭医护人员调度问题研究

为了减少医护人员调度成本，提高客户满意度，研究了家庭医疗护理人员调度问题。考虑客户具有多个可接受服务的时间窗，并对不同时间窗具有不同偏好的特性，建立以总运营成本最小、满意度最大为目标的数学模型。基于Dantzig-Wolfe分解原理将所建模型重构为集合划分主问题和含多时间窗的最短路径子问题模型。运用将列生成嵌入分支定界框架中的分支定价算法对问题求解，并根据多时间窗的问题特性设计了快速获得初始解的随机贪心算法和求解子问题的改进标签算法。对50组算例进行测试，将所提出的算法与CPLEX对比，验证了算法的有效性。最后比较单时间窗和多时间窗算例结果发现，客户提供多个可接受服务的时间窗能有效降低调度成本。     

连续泊位分配问题研究:模型优化与计算分析

研究了船舶动态到港情况下的连续泊位分配问题。对Imai模型进行了分析,指出其非线性约束数量是关于到港船舶数量的二次函数,呈幂数级增长,增加了精确算法的求解难度。通过设置新的变量、重新规划时间序列与空间序列等约束条件,构建了新的混合整数非线性规划模型,有效地减少了非线性约束数量,提高了分支定界算法的求解效率。考虑到问题的NP-hard特性,设计了解决大规模问题的遗传算法。实验算例表明,与Imai模型相比,新模型在求解时间方面更具优势;而所设计的遗传算法,与LINGO软件相比,则能在合理的时间内有效解决泊位分配的大规模优化问题。     

设施数目不确定情况下的截流选址问题

由于选址决策的长期性,相关参数会随着时间而变化,所以选址问题存在很多不确定因素.针对在最终设施数目不确定,但已知相应概率的情形下,研究了如何选择初始设施的位置,使得期望值最大的截流选址问题,并建立了整数规划模型.在此基础上给出了未来至多新建一个设施时的启发式算法,并通过算例,与分支定界法进行比较.结果表明,该算法能得到较好的结果.     

面向节能无关联平行机调度模型及分支定界法

工业企业,特别是高耗能行业,不仅要满足交货期和缩小生产周期的要求,而且不断优化能源配置,降低能耗。研究一类新的以延迟和能源消耗的加权最小为目标的生产调度问题。首先,描述问题并分析问题的复杂性。其次,建立混合整数线性规划模型。进一步,我们提出求解该问题的分支定界算法。最后,通过数值实验和数值试验,验证算法的有效性和高效性。     

不定整数二次规划的一个新的分支定界算法

本文通过正交变换及凹函数的线性下方估计得到不定整数二次规划的可分离形式的连续凸松弛问题,然后利用Lagrangian对偶技术导出该凸松弛问题最优值的Lagrangian对偶下界,再结合超矩形整数对分,建立了一个求解不定整数二次规划新的分支定界算法。最后给出了数值试验对结果进行了比较。     

基于成本/收益权衡的多元需求FIP选址研究

需求种类分析对选址决策至关重要,考虑了消费者需求种类为多元化,且各类需求间有影响的网络上截流(FIP)选址问题,引入路径上需求损失函数,建立了收益最大和总的建设成本最小的双目标的多元需求FIP(mDFIP)的新模型。所建立的模型为NP-hard问题,设计了多目标演化算法求解模型,最后通过具体的算例与基于ε约束法的分支定界法进行比较,结果表明在求解效率上多目标演化算法具有很大优势。     

带有界约束非凸二次规划问题的整体优化方法

通过研究带有界约束非凸二次规划问题，给出了求解该问题的整体最优 解的分枝定界方法及其收敛性，提出了定界的紧，松驰策略，把球约束二次规划问题作为子问题来确定原问题的整体最优值下界和上界，应用分枝定界方法达到了对原问题的求解。     

Designing an Assembly Process with Stochastic Material Arrivals

Due to product proliferation and quick changes in manufacturing materials sourcing partnerships, assembly process in the electronic assembly industry is frequently altered or new processes are introduced. The most appropriate assembly process is critical for companies to maintain an effective supply chain. We study the problem of how to design an assembly process that relies on the stochastic arrival times of parts and components such that the probability of on-time delivery of finished products is maximized. We first provide some analytical results for cases that are polynomially solvable and then provide a branch and bound algorithm for deriving an optimal solution to the problem. We also provide heuristic algorithms to solve the problem. Finally, computational experiments show that our heuristic algorithms perform very well.     

Two-machine flow shop problem with unit-time operations and conflict graph

This paper addresses the problem of scheduling, on a two-machine flow shop, a set of unit-time operations subject to the constraints that some conflicting jobs cannot be scheduled simultaneously on different machines. In the context of our study, these conflicts are modelled by general graphs. The problem of minimising the maximum completion time (makespan) is known to be NP-hard in the strong sense. We propose a mixed-integer linear programming (MILP) model. Then, we develop a branch and bound algorithm based on new lower and upper bound procedures. We further provide a computer simulation to measure the performance of the proposed approaches. The computational results show that the branch and bound algorithm outperforms the MILP model and can solve instances of size up to 20,000 jobs.     

Scheduling jobs on unrelated parallel machines to minimize regular total cost functions

In this paper we consider unrelated parallel machine scheduling problems that involve the minimization of regular total cost functions. We first present some properties of optimal solutions and then provide a lower bound. These mechanisms are tested on the well-known practical problem of minimizing total weighted flow time on unrelated parallel machines. In doing so, we design a branch and bound algorithm incorporating the mechanisms derived for the general total cost function along with the ones derived specifically for the total weighted flow time criterion. Computational experience indicates that incoiporating reduction and bounding mechanisms significantly improves the performance of the branch and bound algorithm.     

Spread time considerations in operational fixed job scheduling

In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.     

A branch and bound algorithm for optimal cyclic scheduling in a robotic cell with processing time windows

A branch and bound algorithm is described for optimal cyclic scheduling in a robotic cell with processing time windows. The objective is to minimise the cycle time by determining the exact processing time on each machine which is limited within a time window. The problem is formulated as a set of prohibited intervals of the cycle time, which is usually applied in the robotic cyclic scheduling problem with fixed processing times. Since both bounds of these prohibited intervals are linear expressions of the processing times, we divide these prohibited intervals into a series of the subsets and transform the problem into enumerating the non-prohibited intervals of cycle time in each subset. This enumeration procedure is completed by an efficient branch and bound algorithm, which could find an optimal solution by enumerating partial non-prohibited intervals. Computational results on the benchmark instances and randomly generated test instances indicate that the algorithm is effective.     

A vector space model for variance reduction in single machine scheduling

Reducing the variance of part completion times about promised due dates is an important element of Just-In-Time production because it reduces the work-in-process inventory and tardiness simultaneously. Scheduling models and algorithms are developed to minimize the Mean Squared Deviation (MSD) of completion times about due dates on a single machine. A generic model is developed in real vector space for understanding the structural relationship between the optimal schedule and the location of the due dates. Geometric insights gained from this vector space model are used to relate the shortest and longest processing time sequences to the level of difficulty of the MSD optimization problem. The vector space model is used to develop dominance conditions for a branch and bound algorithm and to analytically synthesize parameters for a continuous variable feedback control algorithm for distributed scheduling. The control algorithm lends itself to massively parallel / distributed computation and is found to produce near optimal solutions efficiently, which makes it more scalable and practical compared to the branch and bound algorithm. Computational experiments with both approaches are presented.     

Design of flexible assembly line to minimize equipment cost

In this paper we develop an optimal and a heuristic algorithm for the problem of designing a flexible assembly line when several equipment alternatives are available. The design problem addresses the questions of selecting the equipment and assigning tasks to workstations, when precedence constraints exist among tasks. The objective is to minimize total equipment costs, given a predetermined cycle time (derived from the required production rate). We develop an exact branch and bound algorithm which is capable of solving practical problems of moderate size. The algorithm's efficiency is enhanced due to the development of good lower bounds, as well as the use of some dominance rules to reduce the size of the branch and bound tree. We also suggest the use of a branch-and-bound-based heuristic procedure for large problems, and analyze the design and performance of this heuristic.