Two-machine flow shop scheduling problem with an outsourcing option

We consider a two-machine flow shop problem in which each job is processed through an in-house system or outsourced to a subcontractor. A schedule is established for the in-house jobs, and performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and total outsourcing costs. We show that the problem is NP-hard in the ordinary sense. We consider a special case in which each job has a processing requirement, and each machine a characteristic value. In this case, the time a job occupies a machine is equal to the job’s processing requirement plus a setup time equal to the characteristic value of that machine. We introduce some optimality conditions and present a polynomial-time algorithm to solve the special case.     

Single courier single restaurant meal delivery (without routing)

We investigate optimization models for meal delivery that do not involve routing. We focus on the simplest case, with a single restaurant and a single courier, and reduce it to the throughput maximization single machine scheduling problem, with release times and bounded slacks. In the meal delivery setting, slacks are small for QoS purposes and we indeed show that the scheduling problem can be solved in polynomial time when slacks are bounded. We discuss extensions to more couriers and restaurants.     

Star partitions on graphs

Given an undirected graph, a star partition is a partition of the nodes into subsets with at least two nodes so that the subgraph induced by each subset has a spanning star. Star partitions are related to well-known problems concerning domination in graphs and edge covering. We focus on the Constrained Star Partition Problem (CSP) that asks for finding a star partition of given cardinality. The problem is new and presents interesting peculiarities. We explore the relation between the cardinalities of star partitions and domatic bipartitions, showing that there are star partitions of any cardinality between minimum and maximum values, and that a similar but weaker result holds for domatic bipartitions. We study the computational complexity of different versions of star partition and domatic bipartition problems, proving that most of them, in particular CSP, constrained domatic bipartition and balanced domatic bipartition, are NP-complete. We also show that star partition problems are polynomial on trees and, more generally, on bounded treewidth graphs. We introduce an integer linear programming formulation that defines a polytope containing all the star partitions of a graph, showing that its vertices have only integral components for trees, which implies that linear programming can be used to solve weighted star partition problems on trees.     

无线通信系统设计中的两个优化问题和相关优化方法

无线通信系统设计中的许多问题可建模为优化问题.一方面,这些优化问题常常具有高度的非线性性,一般情况下难于求解;另一方面,它们又有自身的特殊结构,例如隐含的凸性、可分性等.利用优化的方法结合问题的特殊结构求解和处理无线通信系统设计问题是近年来学术界研究的热点.本文重点讨论无线通信系统设计中的两个优化问题和相关优化方法,包括多用户干扰信道最大最小准则下的联合传输/接收波束成形设计和多输入多输出(Multi-Input Multi-Output,MIMO)检测问题,主要介绍现代优化技术结合问题的特殊结构在求解和处理上述两个问题的最新进展.     

线性权互补问题的新全牛顿步可行内点算法

基于一个连续可微函数,通过等价变换中心路径,给出求解线性权互补问题的一个新全牛顿步可行内点算法.该算法每步迭代只需求解一个线性方程组,且不需要进行线搜索.通过适当选取参数,分析了迭代点的严格可行性,并证明算法具有线性优化最好的多项式时间迭代复杂度.数值结果验证了算法的有效性.     

Information-theoretical complexity for the hydrogenic abstraction reaction

In this work, we have investigated the complexity of the hydrogenic abstraction reaction by means of information functionals such as disequilibrium (D), exponential entropy (L), Fisher information (I), power entropy (J) and joint information-theoretic measures, i.e. the I–D, D–L and I–J planes and the Fisher–Shannon and López–Mancini–Calbet (LMC) shape complexities. The analysis of the information-theoretical functionals of the one-particle density was computed in position (r) and momentum (p) space. The analysis revealed that all of the chemically significant regions can be identified from the information functionals and most of the information-theoretical planes, i.e. the reactant/product regions (R/P), the transition state (TS), including those that are not present in the energy profile such as the bond cleavage energy region (BCER), and the bond breaking/forming regions (B–B/F). The analysis of the complexities shows that, in position as well as in the joint space, the energy profile of the abstraction reaction bears the same information-theoretical features as the LMC and FS measures. We discuss why most of the chemical features of interest, namely the BCER and B–B/F, are lost in the energy profile and that they are only revealed when particular information-theoretical aspects of localizability (L or J), uniformity (D) and disorder (I) are considered.     

一类具有Markov性质的混沌系统的构造

本文构造了一类具有Markov性质的分段扩张线性映射, 计算表明其具有正的李雅普诺夫指数. 通过理论分析, 证明了其极限分布是均匀分布, 并给出了其最小周期的计算公式. 通过分析符号熵测度应用于此系统时的具体涵义, 指出该系统的复杂度与系统的最小周期之间存在着矛盾关系, 说明了此系统具有可控的复杂度并给出了其复杂度随系统参数变化时的理论极限公式. 通过统计测试和复杂度测试表明, 此系统产生的混沌序列服从均匀分布, 而通过参数的调整该系统的符号熵可以接近其理论极限, 而与Logistic映射和斜帐篷映射的基于近似熵和符号熵的对比实验可知, 本文所提系统具有更高的复杂度, 并有更长的最小周期. 这表明此系统比较适合用于构造保密通信系统. 关键词： 混沌 Markov性质 复杂度 均匀分布     

结构多项式复杂性研究中使用的一些方法

本文介绍了结构多项式复杂性研究中用的一些方法，包括能行对角线方法，能行有穷延伸法，填料法，间隙法，延迟对角线法，加速法。