A heuristic procedure for solving the dynamic probabilistic project expediting problem

Because of activity duration uncertainties, large-scale projects can often be modeled most realistically as probabilistic activity networks. The complex interactions among activities with uncertain durations virtually assures a low probability that these projects will be completed before predetermined due dates. As a result, it is often necessary to expedite individual activities in these projects to improve due date performance. This research introduces a dynamically applied matrix simulation approach for selecting expediting options in order to control the probability of successful project completion before predefined due dates. Experiments are conducted to demonstrate the ability of this new approach to generate quality alternatives and efficiently evaluate large-scale projects.     

Exact and heuristic methods for placing ships in locks

The ship placement problem constitutes a daily challenge for planners in tide river harbours. In essence, it entails positioning a set of ships into as few lock chambers as possible while satisfying a number of general and specific placement constraints. These constraints make the ship placement problem different from traditional 2D bin packing. A mathematical formulation for the problem is presented. In addition, a decomposition model is developed which allows for computing optimal solutions in a reasonable time. A multi-order best fit heuristic for the ship placement problem is introduced, and its performance is compared with that of the left-right-left-back heuristic. Experiments on simulated and real-life instances show that the multi-order best fit heuristic beats the other heuristics by a landslide, while maintaining comparable calculation times. Finally, the new heuristic’s optimality gap is small, while it clearly outperforms the exact approach with respect to calculation time.     

A heuristic method to rectify intransitive judgments in pairwise comparison matrices

This paper investigates the effects of intransitive judgments on the consistency of pairwise comparison matrices. Statistical evidence regarding the occurrence of intransitive judgements in pairwise matrices of acceptable consistency is gathered by using a Monte-Carlo simulation, which confirms that relatively high percentage of comparison matrices, satisfying Saaty’s CR criterion are ordinally inconsistent. It is also shown that ordinal inconsistency does not necessarily decrease in the group aggregation process, in contrast with cardinal inconsistency. A heuristic algorithm is proposed to improve ordinal consistency by identifying and eliminating intransitivities in pairwise comparison matrices. The proposed algorithm generates near-optimal solutions and outperforms other tested approaches with respect to computation time.     

A skyline heuristic for the 2D rectangular packing and strip packing problems

In this paper, we propose a greedy heuristic for the 2D rectangular packing problem (2DRP) that represents packings using a skyline; the use of this heuristic in a simple tabu search approach outperforms the best existing approach for the 2DRP on benchmark test cases. We then make use of this 2DRP approach as a subroutine in an “iterative doubling” binary search on the height of the packing to solve the 2D rectangular strip packing problem (2DSP). This approach outperforms all existing approaches on standard benchmark test cases for the 2DSP.     

中小企业环境与经济协调发展的决策支持系统

本文分析了中小企业环境与经济协调发展的基本机理，开发了基于环保投资的决策支持系统，为中小企业环境与经济协调发展提供决策支持工具．     

Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting

This paper presents a priority rule-based heuristic for the multi-mode resource-constrained project scheduling problem with the splitting of activities around unavailable resources allowed. All resources considered are renewable and each resource unit may not be available at all times due to resource vacations, which are known in advance. A new concept called moving resource strength is developed to help identify project situations where activity splitting is likely to be beneficial during scheduling. The moving resource strength concept is implemented in priority rule-based heuristics to control activity splitting when scheduling. Multiple comparisons of the performance of combination of activity–mode priority rules used in the heuristics are provided. Computational experiments demonstrate the effectiveness of the heuristic in reducing project makespan, and minimizing activity splitting.     

因子分析法在中小企业板块上市公司综合业绩评价中的应用

本文运用因子分析法对我国中小企业板块22家上市公司的综合业绩进行评价,从其2003年度十三个主要财务指标中提取了四个具有一定含义的因子,用它们代表各公司的综合业绩,根据每家公司的因子得分情况对其综合业绩排序。     

A heuristic method for RCPSP with fuzzy activity times

In this paper, we propose a heuristic method for resource constrained project scheduling problem with fuzzy activity times. This method is based on priority rule for parallel schedule generation scheme. Calculation of critical path in this case requires comparison of fuzzy numbers. Distance based ranking of fuzzy number is used for finding the critical path length and concept of shifting criticality is proposed for some of the special cases. We also propose a measure for finding the non-integer power of a fuzzy number. We discuss some properties of the proposed method. We use an example to illustrate the method.     

中小企业技术创新网络的演化分析

在中小企业技术创新网络中,企业是否参加技术创新及其参与比例直接影响企业网络整体的技术创新。本文以技术创新网络中的小型企业和微型企业为例,建模博弈分析同时或先后技术创新情形下,二者都开展技术创新、只有一个企业技术创新或者都不创新时的收益,随后运用进化博弈理论分析企业参与技术创新的顺序及其比例如何影响网络技术创新的稳定性,指出了企业技术创新网络演进的条件。这一结论对于认识中小企业技术创新网络及其网络技术创新管理具有一定的意义。     

A disjunctive graph model and framework for constructing new train schedules

Train scheduling is a complex and time consuming task of vital importance in many countries. To create completely new train schedules that are more accurate and efficient than permitted by current techniques, a novel “hybrid” job shop approach is proposed and implemented in this paper. Unique characteristics of train scheduling are firstly incorporated into a disjunctive graph representation of the solution. Dedicated “stand-alone” constructive algorithms that utilise this representation are then developed. The modelling approach and the constructive algorithms are essential as they provide the basis for which meta-heuristics and other iterative refinement algorithms can be applied. A numerical investigation and case study is provided and demonstrates the viability of the modelling approach. Furthermore it is demonstrated that good quality solutions are provided with reasonable computational effort.     

A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem

This paper is concerned with the development of intelligent decision support methodologies for nurse rostering problems in large modern hospital environments. We present an approach which hybridises heuristic ordering with variable neighbourhood search. We show that the search can be extended and the solution quality can be significantly improved by the careful combination and repeated use of heuristic ordering, variable neighbourhood search and back-tracking. The amount of computational time that is allowed plays a significant role and we analyse and discuss this. The algorithms are evaluated against a commercial Genetic Algorithm on commercial data. We demonstrate that this methodology can significantly outperform the commercial algorithm. This paper is one of the few in the scientific nurse rostering literature which deal with commercial data and which compare against a commercially implemented algorithm.     

A graph-pair representation and MIP-model-based heuristic for the unequal-area facility layout problem

Owing to its theoretical as well as practical significance, the facility layout problem with unequal-area departments has been studied for several decades, with a wide range of heuristic and a few exact solution procedures developed by numerous researchers. In one of the exact procedures, the facility layout problem is formulated as a mixed-integer programming (MIP) model in which binary (0/1) variables are used to prevent departments from overlapping with one another. Obtaining an optimal solution to the MIP model is difficult, and currently only problems with a limited number of departments can be solved to optimality. Motivated by this situation, we developed a heuristic procedure which uses a “graph pair” to determine and manipulate the relative location of the departments in the layout. The graph-pair representation technique essentially eliminates the binary variables in the MIP model, which allows the heuristic to solve a large number of linear programming models to construct and improve the layout in a comparatively short period of time. The search procedure to improve the layout is driven by a simulated annealing algorithm. The effectiveness of the proposed graph-pair heuristic is demonstrated by comparing the results with those reported in recent papers. Possible extensions to the graph-pair representation technique are discussed at the end of the paper.     

A heuristic for the multi-period petrol station replenishment problem

In the multi-period petrol station replenishment problem (MPSRP) the aim is to optimize the delivery of several petroleum products to a set of petrol stations over a given planning horizon. One must determine, for each day of the planning horizon, how much of each product should be delivered to each station, how to load these products into vehicle compartments, and how to plan vehicle routes. The objective is to maximize the total profit equal to the revenue, minus the sum of routing costs and of regular and overtime costs. This article describes a heuristic for the MPSRP. It contains a route construction and truck loading procedures, a route packing procedure, and two procedures enabling the anticipation or the postponement of deliveries. The heuristic was extensively tested on randomly generated data and compared to a previously published algorithm. Computational results confirm the efficiency of the proposed methodology.     

A scatter search algorithm for project scheduling under partially renewable resources

In this paper we develop a heuristic algorithm, based on Scatter Search, for project scheduling problems under partially renewable resources. This new type of resource can be viewed as a generalization of renewable and non-renewable resources, and is very helpful in modelling conditions that do no fit into classical models, but which appear in real timetabling and labor scheduling problems. The Scatter Search algorithm is tested on existing test instances and obtains the best results known so far.     

Combining integer programming and the randomization method to schedule employees

We describe a method to find low cost shift schedules with a time-varying service level that is always above a specified minimum. Most previous approaches used a two-step procedure: (1) determine staffing requirements and (2) find a minimum cost schedule that provides the required staffing in every period. Approximations in the first step sometimes cause the two-step approach to find infeasible or suboptimal solutions. Our method iterates between a schedule evaluator and a schedule generator. The schedule evaluator calculates transient service levels using the randomization method and identifies infeasible intervals, where the service level is lower than desired. The schedule generator solves a series of integer programs to produce improved schedules, by adding constraints for every infeasible interval, in an attempt to eliminate infeasibility without eliminating the optimal solution. We present computational results for several test problems and discuss factors that make our approach more likely to outperform previous approaches.     

中小企业融资中的逆向选择和道德风险

针对我国中小企业融资难的难题,利用博弈论和信息经济学的有关理论知识,从定量的角度深入分析了中小企业融资中逆向选择和道德风险的形成过程和机理,从理论上论证了中小企业融资难的重要原因在于中小企业与金融机构之间信息分布的非对称,在此基础上并给出了降低或规避逆向选择和道德风险的途径.     

A problem expanding parametric programming method for solving the job shop scheduling problem

A new zero-one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts: (a) a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time; (b) a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to thirty-six operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling

In this study, a general framework is proposed that combines the distinctive features of three well-known approaches: the adaptive memory programming, the simulated annealing, and the tabu search methods. Four variants of a heuristic based on this framework are developed and presented. The performance of the proposed methods is evaluated and compared with a conventional simulated annealing approach using benchmark problems for job shop scheduling. The unique feature of the proposed framework is the use of two short-term memories. The first memory temporarily prevents further changes in the configuration of a provisional solution by maintaining the presence of good elements of such solutions. The purpose of the second memory is to keep track of good solutions found during an iteration, so that the best of these can be used as the starting point in a subsequent iteration. Our computational results for the job shop scheduling problem clearly indicate that the proposed methods significantly outperform the conventional simulated annealing.     

A hybrid heuristic for a multi-objective real-life car sequencing problem with painting and assembly line constraints

We address a multi-objective version of the car sequencing problem, which consists in sequencing a given set of cars to be produced in a single day, minimizing the number of violations of assembly constraints and the number of paint color changes in the production line. We propose a set of heuristics for approximately solving this problem, based on the paradigms of the VNS and ILS metaheuristics, to which further intensification and diversification strategies have been added. Computational results on real-life test instances are reported. The work presented in this paper obtained the second prize in the ROADEF challenge 2005 sponsored by Renault.     

A heuristic for the long-term electricity generation planning problem using the Bloom and Gallant formulation

Long-term power planning is a stochastic problem often confronted by electrical utilities in liberalized markets. One can model it for profit maximization—using market-price estimation functions for each interval—by posing it as a quadratic programming problem with some linear equalities and an exponential number of load-matching linear inequality constraints.