软件项目支付进度问题研究

软件项目的复杂性和特点使得其支付进度问题较具特殊性。针对软件质量的差异性,对软件项目支付进度问题进行研究。以承包商净现值最大化为优化目标,构建了具有惩罚结构的支付进度优化模型,该模型反映了不同软件质量对承包商收益的影响;针对该问题的特点设计了启发式求解算法;最后通过一个算例对模型进行了验证。可为承包商在签订外包合同及外包实施中的策略提供决策依据。     

有关单机两代理排序问题的两个结果

研究了两个单机两代理排序问题. 在第一个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化最大工件费用. 在第二个两代理排序问题中, 代理A的目标函数为极小化所有工件的加权完工时间总和, 代理B的目标函数为极小化所有工件的最大完工时间. 证明了第一个问题是强NP-难的, 改进了已有的一般意义NP-难的结果; 对第二个问题给出了一个与现有的动态规划算法不同的动态规划算法.     

光突发交换边缘路由器性能分析

本文详细分析了各种因素对光突发交换边缘路由器的性能的影响.结果显示,不同服务等级的时延要求可以通过控制组装的最大时延得以保证;不同等级数据包长的大范围变动会导致信道分配的不公平性;边缘节点越多,丢包率越高;在总输出容量一定的情况下,增加输出数据信道数可以在获得低的丢包率的同时达到较高的通道利用率,但随着边缘节点数的增加,增加输出信道数对丢包率的改善作用下降.     

机器维修的排序问题

研究了机器维修的排序问题,假设第i台机器的维修起始日期为第αi天(i=1,2,…,n)．n台机器的维修起始日期简记为(α1,α2,…,αn),得到一系列(α1,α2,…,αn)存在的充分或必要条件。     

Interconnection networks for parallel molecular dynamics simulation based on hamiltonian cubic symmetric topology

A class of interconnection networks for efficient parallel MD simulations based on hamiltonian cubic symmetric graphs is presented. The cubic symmetric graphs have many desirable properties as interconnection networks since they have a low degree and are vertex- and edge-transitive. We present a method for scheduling collective communication routines that are used in parallel MD and are based on the property that the graphs in question have a Hamilton cycle, that is, a cycle going through all vertices of the graph. Analyzing these communication routines shows that hamiltonian cubic symmetric graphs of small diameter are good candidates for a topology that gives rise to an interconnection network with excellent properties, allowing faster communication and thus speeding up parallel MD simulation.     

Permutation-induced acyclic networks for the job shop scheduling problem

In the literature of the combinatorial optimization problems, it is a commonplace to find more than one mathematical model for the same problem. The significance of a model may be measured in terms of the efficiency of the solution algorithms that can be built upon it. The purpose of this article is to present a new network model for the well known combinatorial optimization problem – the job shop scheduling problem. The new network model has similar structure as the disjunctive graph model except that it uses permutations of jobs as decision variables instead of the binary decision variables associated with the disjunctive arcs. To assess the significance of the new model, the performances of exact branch-and-bound algorithmic implementations that are based on both the new model and the disjunctive graph model are compared.     

A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling

We develop a heuristic procedure for solving the discrete time/resource trade-off problem in the field of project scheduling. In this problem, a project contains activities interrelated by finish-start-type precedence constraints with a time lag of zero, which require one or more constrained renewable resources. Each activity has a specified work content and can be performed in different modes, i.e. with different durations and resource requirements, as long as the required work content is met. The objective is to schedule each activity in one of its modes in order to minimize the project makespan. We use a scatter search algorithm to tackle this problem, using path relinking methodology as a solution combination method. Computational results on randomly generated problem sets are compared with the best available results indicating the efficiency of the proposed algorithm.     

Analysis,modeling and solution of the concrete delivery problem

This paper describes a specific local search approach to solve a problem arising in logistics which we prove to be NP-hard. The problem is a complex scheduling or vehicle routing problem where we have to schedule the tours of concrete mixer vehicles over a working day from concrete-producing depots to concrete-demanding customers and vice versa. We give a general mixed integer programming model which is too hard to solve for state of the art mixed integer programming optimizers in the case of the usually huge problem instances coming from practice. Therefore we present a certain local search approach to be able to handle huge practical problem instances.     

A hybrid genetic local search algorithm for the permutation flowshop scheduling problem

Traditionally, the permutation flowshop scheduling problem (PFSP) was with the criterion of minimizing makespan. The permutation flowshop scheduling problem to minimize the total flowtime has attracted more attention from researchers in recent years. In this paper, a hybrid genetic local search algorithm is proposed to solve this problem with each of both criteria. The proposed algorithm hybridizes the genetic algorithm and a novel local search scheme that combines two local search methods: the Insertion Search (IS) and the Insertion Search with Cut-and-Repair (ISCR). It employs the genetic algorithm to do the global search and two local search methods to do the local search. Two local search methods play different roles in the search process. The Insertion Search is responsible for searching a small neighborhood while the Insertion Search with Cut-and-Repair is responsible for searching a large neighborhood. Furthermore, the orthogonal-array-based crossover operator is designed to enhance the GA’s capability of intensification. The experimental results show the advantage of combining the two local search methods. The performance of the proposed hybrid genetic algorithm is very competitive. For the PFSP with the total flowtime criterion, it improved 66 out of the 90 current best solutions reported in the literature in short-term search and it also improved all the 20 current best solutions reported in the literature in long-term search. For the PFSP with the makespan criterion, the proposed algorithm also outperforms the other three methods recently reported in the literature.     

Minimizing the number of machines for scheduling jobs with equal processing times

In this paper, we consider a parallel machine environment when all jobs have the same processing time and arbitrary release dates and deadlines of the jobs are given. We suppose that the available number of machines, which can be used simultaneously, may vary over time. The aim is to construct a feasible schedule in such a way that the maximal number of simultaneously used machines is minimal. We give a polynomial algorithm for this problem.