Openshop scheduling under linear resources constraints

Consider n jobs (J₁, …, J_n), m working stations (M₁, …, M_m) and λ linear resources (R₁, …, R_λ). Job J_i consists of m operations (O_i1, …, O_im). Operation O_ij requires P_k(i, j) units of resource R_k to be realized in an M_j. The availability of resource R_k and the ability of the working station M_h to consume resource R_k, vary over time. An operation involving more than one resource consumes them in constant proportions equal to those in which they are required. The order in which operations are realized is immaterial. We seek an allocation of the resources such that the schedule length is minimized. In this paper, polynomial algorithms are developed for several problems, while NP-hardness is demonstrated for several others. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 51–66, 1998     

Oligopolistic contracting: Channel coordination under competition

We study contracts between a single retailer and multiple suppliers of two substitutable products, where suppliers have fixed capacities and present the retailer cost contracts for their supplies. After observing the contracts, the retailer decides how much capacity to purchase from each supplier, to maximize profits from the purchased capacity from the suppliers plus his possessed inventory (endowment). This is modeled as a noncooperative, nonzero‐sum game, where suppliers, or principals, move simultaneously as leaders and the retailer, the common agent, is the sole follower. We are interested in the form of the contracts in equilibrium, their effect on the total supply chain profit, and how the profit is split between the suppliers and the retailer. Under mild assumptions, we characterize the set of all equilibrium contracts and discuss all‐unit and marginal‐unit quantity discounts as special cases. We also show that the supply chain is coordinated in equilibrium with a unique profit split between the retailer and the suppliers. Each supplier's profit is equal to the marginal contribution of her capacity to supply chain profits in equilibrium. The retailer's profit is equal to the total revenue collected from the market minus the payments to the suppliers and the associated sales costs.     

Dynamic pricing under first order Markovian competition

We evaluate the effect of competition on prices, profits, and consumers' surplus in multiperiod, finite horizon, dynamic pricing settings. In our base model, a single myopic consumer visits two competing retailers, who offer identical goods, in a (first order Markovian) probabilistic fashion—if the posted price exceeds the consumer's valuation for the good, he returns to the same store in the following period with a certain probability. We find that even a small reduction in the return probability from one—which corresponds to the monopoly case at which prices decline linearly—is sufficient to revert the price decline from a linear into an exponential shape. Each retailer's profit is particularly sensitive to changes in his return probability when it is relatively high, and is maximized under complete loyalty behavior (i.e., return probability is one). On the other hand, consumer surplus is maximized under complete switching behavior (i.e., return probability is zero). In the presence of many similar consumers, the insights remain valid. We further focus on the extreme scenario where all consumers follow a complete switching behavior, to derive sharp bounds, and also consider the instance where, in this setting, myopic consumers are replaced with strategic consumers. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Evergreening and operational risk under price competition

“Evergreening” is a strategy wherein an innovative pharmaceutical firm introduces an upgrade of its current product when the patent on this product expires. The upgrade is introduced with a new patent and is designed to counter competition from generic manufacturers that seek to imitate the firm's existing product. However, this process is fraught with uncertainty because the upgrade is subject to stringent guidelines and faces approval risk. Thus, an incumbent firm has to make an upfront production capacity investment without clarity on whether the upgrade will reach the market. This uncertainty may also affect the capacity investment of a competing manufacturer who introduces a generic version of the incumbent's existing product but whose market demand depends on the success or failure of the upgrade. We analyze a game where capacity investment occurs before uncertainty resolution and firms compete on prices thereafter. Capacity considerations that arise due to demand uncertainty introduce new factors into the evergreening decision. Equilibrium analysis reveals that the upgrade's estimated approval probability needs to exceed a threshold for the incumbent to invest in evergreening. This threshold for evergreening increases as the intensity of competition in the generic market increases. If evergreening is optimal, the incumbent's capacity investment is either decreasing or nonmonotonic with respect to low end market competition depending on whether the level of product improvement in the upgrade is low or high. If the entrant faces a capacity constraint, then the probability threshold for evergreening is higher than the case where the entrant is not capacity constrained. Finally, by incorporating the risk‐return trade‐off that the incumbent faces in terms of the level of product improvement versus the upgrade success probability, we can characterize policy for a regulator. We show that the introduction of capacity considerations may maximize market coverage and/or social surplus at incremental levels of product improvement in the upgrade. This is contrary to the prevalent view of regulators who seek to curtail evergreening involving incremental product improvement. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 71–89, 2016     

Project scheduling: The effects of problem structure on heuristic performance

Individual characteristics of multiple-constrained resource, project scheduling problems are examined in an attempt to predict the solution obtainable with heuristic methods. Difficulties encountered in performing this type of research are described, and several multiple regression models are developed for predicting heuristic performance. Both single and multiple project data are examined, and results reported demonstrate the efficacy of determining beforehand the method used for problem solution.     

Production-allocation scheduling and capacity expansion using network flows under uncertainty

This paper extends Connors and Zangwill's work in network flows under uncertainty to the convex costs case. In this paper the extended network flow under uncertainty algorithm is applied to compute N-period production and delivery schedules of a single commodity in a two-echelon production-inventory system with convex costs and low demand items. Given an initial production capacity for N periods, the optimal production and delivery schedules for the entire N periods are characterized by the flows through paths of minimal expected discounted cost in the network As a by-product of this algorithm the multi-period stochastic version of the parametric budget problem for the two-echelon production-inventory system is solved.     

A multiple‐shift workforce scheduling model under annualized hours

Many manufacturing and service organizations in Europe have used annualized hours, also known as flexiyear, to successfully tackle seasonal demand. Under annualized hours, the employer has a certain number of labor hours available in a year and the employer can allocate the hours over the year according to manpower need. A problem in planning for annualized hours is the scheduling of the workforce over the year. We present an algorithm to generate an annual schedule for a scenario in which a facility operates one or more shifts and manpower need may vary from week to week. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 726–736, 1999     

A nonatomic‐game model for timing clearance sales under competition

We deal with dynamic revenue management (RM) under competition using the nonatomic‐game approach. Here, a continuum of heterogeneous sellers try to sell the same product over a given time horizon. Each seller can lower his price once at the time of his own choosing, and faces Poisson demand arrival with a rate that is the product of a price‐sensitive term and a market‐dependent term. Different types of sellers interact, and their respective prices help shape the overall market in which they operate, thereby influencing the behavior of all sellers. Using the infinite‐seller approximation, which deprives any individual seller of his influence over the entire market, we show the existence of a certain pattern of seller behaviors that collectively produce an environment to which the behavior pattern forms a best response. Such equilibrium behaviors point to the suitability of threshold‐like pricing policies. Our computational study yields insights to RM under competition, such as profound ways in which consumer and competitor types influence seller behaviors and market conditions. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 365–385, 2014     

A self‐adapting genetic algorithm for project scheduling under resource constraints

This papers deals with the classical resource‐constrained project scheduling problem (RCPSP). There, the activities of a project have to be scheduled subject to precedence and resource constraints. The objective is to minimize the makespan of the project. We propose a new heuristic called self‐adapting genetic algorithm to solve the RCPSP. The heuristic employs the well‐known activity list representation and considers two different decoding procedures. An additional gene in the representation determines which of the two decoding procedures is actually used to compute a schedule for an individual. This allows the genetic algorithm to adapt itself to the problem instance actually solved. That is, the genetic algorithm learns which of the alternative decoding procedures is the more successful one for this instance. In other words, not only the solution for the problem, but also the algorithm itself is subject to genetic optimization. Computational experiments show that the mechanism of self‐adaptation is capable to exploit the benefits of both decoding procedures. Moreover, the tests show that the proposed heuristic is among the best ones currently available for the RCPSP. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 433–448, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10029     

大型工程项目集成化管理环境下的知识协同与任务调度

将各个项目单元抽象为不同的知识源,详细分析了集成化管理环境下的知识协同问题,提出了基于权威性加权原则的知识协同处理策略,并就策略修正、协同求解等问题作了分析说明。在此基础上,采取前向调度算法和逆向调度算法相结合的迭代算法,建立了协同工作中的任务调度模型,算例证明,模型能够有效满足各约束条件下任务的增删需求。     

质量工程背景下的高校教学团队建设探讨

高校教学团队建设是本科教育教学质量工程的一项重要内容,也是高校师资队伍建设最有效的组织形式。本文通过对五十多个教学团队的推荐表及建设任务书等相关资料进行搜集、整理及分析,对大学教学团队建设的基本情况进行了总结,分析了存在的问题,并提出了相应对策,为高校教学团队建设提供了依据。     

Transit vessel scheduling

A transit vessel traffic scheduling algorithm has been developed to limit the negative effects on cargo volume throughput in two‐way waterways where separation distances between transiting vessels must be maintained and passage restrictions may hold. It runs in time that is polynomial in the number of ships involved in the computation and finds schedules which increase the utilization of waterways. Three examples illustrate its use. The first example is situated in the Sunda Strait where the algorithm is used to enhance the safety of merchant shipping against a terrorist threat. It illustrates important features of the algorithm and demonstrates how it can be used with cross traffic. The second example is situated in the Strait of Istanbul and offers a comparison between the developed algorithm and the transit vessel scheduling algorithm of Ulusçu et al., J Navig 62 (2009), 59–77. This was done using a plausible model of the Strait of Istanbul. The third and last example shows how the algorithm can be used to schedule transit vessel traffic in two‐way waterways with junctions. This feature is especially useful in congested waters with a high risk of collisions like the Inland Sea of Japan. An extreme test case proves that the developed algorithm is a practical algorithm ready for such use. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 225–248, 2017     

Multiobjective flow-shop scheduling

Previous research on the scheduling of multimachine systems has generally focused on the optimization of individual performance measures. This article considers the sequencing of jobs through a multimachine flow shop, where the quality of the resulting schedule is evaluated according to the associated levels of two scheduling criteria, schedule makespan (C_max) and maximum job tardiness (T_max). We present constructive procedures that quantify the trade-off between C_max and T_max. The significance of this trade-off is that the optimal solution for any preference function involving only C_max and T_max must be contained among the set of efficient schedules that comprise the trade-off curve. For the special case of two-machine flow shops, we present an algorithm that identifies the exact set of efficient schedules. Heruistic procedures for approximating the efficient set are also provided for problems involving many jobs or larger flow shops. Computational results are reported for the procedures which indicate that both the number of efficient schedules and the error incurred by heuristically approximating the efficient set are quite small.     

Integrated production scheduling and preventive maintenance planning for a single machine under a cumulative damage failure process

This paper finds the optimal integrated production schedule and preventive maintenance plan for a single machine exposed under a cumulative damage process, and investigates how the optimal preventive maintenance plan interacts with the optimal production schedule. The goal is to minimize the total tardiness. The optimal policy possesses the following properties: Under arbitrary maintenance plan when jobs have common processing time, and different due dates, the optimal production schedule is to order the jobs by earliest due date first rule; and when jobs have common due date and different processing times, the optimal production schedule is shortest processing time first. The optimal maintenance plan is of control limit type under any arbitrary production schedule when machine is exposed under a cumulative damage failure process. Numerical studies on the optimal maintenance control limit of the maintenance plan indicate that as the number of jobs to be scheduled increases, the effect of jobs due dates on the optimal maintenance control limit diminishes. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

General multiprocessor task scheduling

Most papers in the scheduling field assume that a job can be processed by only one machine at a time. Namely, they use a one‐job‐on‐one‐machine model. In many industry settings, this may not be an adequate model. Motivated by human resource planning, diagnosable microprocessor systems, berth allocation, and manufacturing systems that may require several resources simultaneously to process a job, we study the problem with a one‐job‐on‐multiple‐machine model. In our model, there are several alternatives that can be used to process a job. In each alternative, several machines need to process simultaneously the job assigned. Our purpose is to select an alternative for each job and then to schedule jobs to minimize the completion time of all jobs. In this paper, we provide a pseudopolynomial algorithm to solve optimally the two‐machine problem, and a combination of a fully polynomial scheme and a heuristic to solve the three‐machine problem. We then extend the results to a general m‐machine problem. Our algorithms also provide an effective lower bounding scheme which lays the foundation for solving optimally the general m‐machine problem. Furthermore, our algorithms can also be applied to solve a special case of the three‐machine problem in pseudopolynomial time. Both pseudopolynomial algorithms (for two‐machine and three‐machine problems) are much more efficient than those in the literature. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 57–74, 1999     

The payment scheduling problem

Large complicated projects with interdependent activities can be described by project networks. Arcs represent activities, nodes represent events, and the network's structure defines the relation between activities and events. A schedule associates an occurrence time with each event: the project can be scheduled in several different ways. We assume that a known amount of cash changes hands at each event. Given any schedule the present value of all cash transactions can be calculated. The payment scheduling problem looks for a schedule that maximizes the present value of all transactions. This problem was first introduced by Russell [2]; it is a nonlinear program with linear constraints and a nonconcave objective. This paper demonstrates that the payment scheduling problem can be transformed into an equivalent linear program. The linear program has the structure of a weighted distribution problem and an efficient procedure is presented for its solution. The algorithm requires the solution of triangular systems of equations with all matrix coefficients equal to ± or 0.     

Some simple scheduling algorithms

This paper considers situations in which jobs require only one operation on a single machine, or on one of a set of identical machines. Penalty-free interruption is allowed. Some simple algorithms are given for finding optimum schedules to minimize maximum lateness and total delay, for the single-machine case, and maximum lateness for a restricted multi-machine case. A simple flow problem formulation permits minimizing maximum lateness for the more general multimachine case.     

项目管理在装备研制合同管理中的应用研究

文章首先明确了装备研制合同项目的概念及其意义,并针对我军装备研制合同管理的现状,提出了基于项目管理模式的装备研制合同管理机构及管理流程。为进一步加强装备研制合同管理,使得装备研制合同得以有效履行提供了可行的方法。     

A transportation problem with competition

The classic transportation problem can be generalized with many carriers and one owner. From the formulation the competition in sense of game theory naturally appears. Here we present and solve this problem using a generalized n-person game. Besides the same composition properties about solutions and regarding zones, related results are considered. Finally, the problem in which there is a modification of the set of destinations assigned to the carriers is also studied.     

武器装备可用性设计对寿命周期费用的影响及控制

可用性设计是装备综合保障分析的重要内容.合适的可用度指标不但要满足装备效能要求,还应满足费用约束条件.为了设计并选择出费效比最高的保障方案,研究了可用性设计对装备寿命周期费用的影响,提出了运用可用度门限值来控制寿命周期费用的方法,并举例说明具体的应用.最后,就保障性设计中的费用权衡问题提出了几点建议.