A practical approach to achieving Agility–a theory of constraints perspective

This article documents an action research (AR) project aimed at identifying the practical steps needed to become an agile manufacturer through a combination of the theory of constraints (TOC) and resource- based view (RBV) approaches in a small to medium enterprise (SME) in the Australian manufacturing sector. To date, lean production has been highlighted as a possible catalyst for creating an agile manufacturer, despite the evidence suggesting that lean manufacturing lacks the responsiveness and adaptability to effectively handle a rapidly changing market place and only works well in a stable environment. A more flexible system of production is required to fully encompass the agile characteristics needed to attain a competitive advantage. This research provides empirical evidence that the TOC perspective can be used as a practical approach for becoming an agile manufacturer. The study provides a workable approach for small firms to achieve ‘Agility’ in practice.     

Algorithms for the workflow satisfiability problem engineered for counting constraints

The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification that satisfies the constraints in the specification. The problem is NP-hard in general, but several subclasses of the problem are known to be fixed-parameter tractable (FPT) when parameterized by the number of steps in the specification. In this paper, we consider the WSP with user-independent counting constraints, a large class of constraints for which the WSP is known to be FPT. We describe an efficient implementation of an FPT algorithm for solving this subclass of the WSP and an experimental evaluation of this algorithm. The algorithm iteratively generates all equivalence classes of possible partial solutions until, whenever possible, it finds a complete solution to the problem. We also provide a reduction from a WSP instance to a pseudo-Boolean (PB) SAT instance. We apply this reduction to the instances used in our experiments and solve the resulting PB SAT problems using SAT4J, a PB SAT solver. We compare the performance of our algorithm with that of SAT4J and discuss which of the two approaches would be more effective in practice.     

等式约束的一种降维运算的信赖域方法

本文给出了解决等式约束问题的一种信赖域算法。算法用Byrd和Omojokun方法计算试探步,但在计算试探步时采取了降维的方法。在不要求约束条件的梯度是列满秩的条件下证明了算法的全局收敛性。     

Application of TOC/OPT rules in a medium sized shop

Abstract

Abstract. Theory of constraints (TOC) and optimized production technology (OPT) are frequently presented as the better options for production control systems. Despite this enthusiasm, there is very little literature on how these principles can be implemented in practice without having to resort to the expensive proprietary software. In this paper we present a case study in which the OPT/TOC ideas were implemented without using the software. Management's major concern was reduction of work in process and increased delivery performance. It was decided to test whether the ideas of OPT/TOC were applicable in this environment and more importantly to which extent these two performance measures could be improved. The paper reports on the methodology used to test the OPT/TOC ideas in this shop and presents some early results of improvement, as well as some new problems which arose due to the new approach.     

AN EXPOSITION OF MULTIPLE CONSTRAINT SCHEDULING AS IMPLEMENTED IN THE GOAL SYSTEM (FORMERLY DISASTERTM)

Since Eli Goldratt first appeared on the scene in the late 1970s, his ideas concerning production management have generated a huge amount of interest, controversy, and misunderstanding. These ideas have been proliferated under several names such as optimized production technology (OPT), drum-buffer-rope (DBR), synchronized manufacturing (SM), and theory of constraints (TOC). Although there seems to be general agreement on the importance of how capacity-constrained resources are scheduled, research aimed at advancing the state of the art for the specific problem addressed by DBR continues to be limited by prior misunderstandings and the lack of a rigorous examination by the academic community. This paper seeks “to advance the state of research on constraint scheduling in several ways. First, it presents a concise history of the evolution of DBR. It then explains the use of rods in constraint scheduling. Next, it presents in detail the solution algorithm incorporated by the Goldratt Institute in their production software and, finally, relates that algorithm to alternative methods. In the process of these activities, several lingering misconceptions are resolved.     

On flexible product-mix decision problems under randomness and fuzziness

This paper considers several models of product-mix decision problems and production planning problems under uncertain conditions, and shows that these are extensional and versatile models for resolving previous product-mix problems. These proposed models include randomness derived from statistical analysis based on historical data, ambiguity of decision maker's intuition and the quality of received information, and flexibility in accomplishing the original plan. Furthermore, given that the upper limit values of some constraints have flexibility, and given a decision maker's level of satisfaction, we propose a flexible product mix of problems using the theory of constraints (TOC), and develop an efficient solution method. We then provide a numerical example that compares our models with some previous basic models. Efficiency of flexibility is obtained when our proposed models are applied to several conditions, such as measurable changes from the expected value of future returns.     

在单资源约束项目中的关键链管理

Dr.Goldratt于1986年提出了Theory of Constraint(TOC),强调以系统的观点来进行项目管理。TOC在项目中的运用被称为关键链管理(CCPM),它着眼于项目的关键链,并利用缓冲器来控制项目进程。本文在单资源约束下,以TOC为核心思想,提出了一个进行关键链管理的方法,从而改进了TOC在项目管理中的可操作性。     

等待时间受限的置换流水车间调度启发式算法

针对等待时间受限的置换流水车间调度问题,分析了其可行解与流水车间调度最优解的关系,给出了计算最大完工时间的有向图,证明了等待时间受限的置换流水车间调度问题的可逆性,并以此为基础提出了一种启发式算法.算法首先根据等待时间受限约束与无等待(no-wait)约束的相似特征,生成初始工件序列集;然后利用问题可逆性给出了复杂度为O(n2m)的插入优化机制,进一步优化初始解.数据实验的结果验证了启发式算法的可行性和有效性.     

Bin packing under linear constraints

In this paper, we study a bin packing problem in which the sizes of items are determined by k linear constraints, and the goal is to decide the sizes of items and pack them into a minimal number of unit sized bins. We first provide two scenarios that motivate this research. We show that this problem is NP-hard in general, and propose several algorithms in terms of the number of constraints. If the number of constraints is arbitrary, we propose a 2-approximation algorithm, which is based on the analysis of the Next Fit algorithm for the bin packing problem. If the number of linear constraints is a fixed constant, then we obtain a PTAS by combining linear programming and enumeration techniques, and show that it is an optimal algorithm in polynomial time when the number of constraints is one or two. It is well known that the bin packing problem is strongly NP-hard and cannot be approximated within a factor 3 / 2 unless P = NP. This result implies that the bin packing problem with a fixed number of constraints may be simper than the original bin packing problem. Finally, we discuss the case when the sizes of items are bounded.     

A genetic algorithm-based decomposition approach to solve an integrated equipment-workforce-service planning problem

We develop a new genetic algorithm to solve an integrated Equipment-Workforce-Service Planning problem, which features extremely large scales and complex constraints. Compared with the canonical genetic algorithm, the new algorithm is innovative in four respects: (1) The new algorithm addresses epistasis of genes by decomposing the problem variables into evolutionary variables, which evolve with the genetic operators, and the optimization variables, which are derived by solving corresponding optimization problems. (2) The new algorithm introduces the concept of Capacity Threshold and calculates the Set of Efficient and Valid Equipment Assignments to preclude unpromising solution spaces, which allows the algorithm to search much narrowed but promising solution spaces in a more efficient way. (3) The new algorithm modifies the traditional genetic crossover and mutation operators to incorporate the gene dependency in the evolutionary procedure. (4) The new algorithm proposes a new genetic operator, self-evolution, to simulate the growth procedure of an individual in nature and use it for guided improvements of individuals. The new genetic algorithm design is proven very effective and robust in various numerical tests, compared to the integer programming algorithm and the canonical genetic algorithm. When the integer programming algorithm is unable to solve the large-scale problem instances or cannot provide good solutions in acceptable times, and the canonical genetic algorithm is incapable of handling the complex constraints of these instances, the new genetic algorithm obtains the optimal or close-to-optimal solutions within seconds for instances as large as 84 million integer variables and 82 thousand constraints.     

Some graph optimization problems with weights satisfying linear constraints

In this paper, we study several graph optimization problems in which the weights of vertices or edges are variables determined by several linear constraints, including maximum matching problem under linear constraints (max-MLC), minimum perfect matching problem under linear constraints (min-PMLC), shortest path problem under linear constraints (SPLC) and vertex cover problem under linear constraints (VCLC). The objective of these problems is to decide the weights that are feasible to the linear constraints, and find the optimal solutions of corresponding graph optimization problems among all feasible choices of weights. We find that these problems are NP-hard and are hard to be approximated in general. These findings suggest us to explore various special cases of them. In particular, we show that when the number of constraints is a fixed constant, all these problems are polynomially solvable. Moreover, if the total number of distinct weights is a fixed constant, then max-MLC, min-PMLC and SPLC are polynomially solvable, and VCLC has a 2-approximation algorithm. In addition, we propose approximation algorithms for various cases of max-MLC.

     

SPECIFICATION AND ESTIMATION OF LOGICALLY CONSISTENT LINEAR MODELS

The implications of constrained dependent and independent variables for model parameters are examined. In the context of linear model systems, it is shown that polyhedral constraints on the dependent variables will hold over the domain of the independent variables when a set of polyhedral constraints is satisfied by the model parameters. This result may be used in parameter estimation, in which case all predicted values of the dependent variables are consistent with constraints on the actual values. Also, the implicit constraints that define the set of parameters for many commonly used linear stochastic models with an error term yield values of the dependent variables consistent with the explicit constraints. Models possessing these properties are termed “logically consistent”.     

Maximizing product mix profitability - what's the best analysis tool

This paper takes a look at product mix profitability and compares several alternative methodologies for selecting the optimal product mix. It is argued that the optimal product mix is not determined using traditional accounting methodologies and that dropping marginally profitable products based on the accounting rules will give you less than optimal profitability. This paper looks at two different ways for coming up with the optimal product mix: one using theory of constraints (TOC) and another using linear programming.     

基于拍卖机制的资源转移时间型动态分布式多项目调度

实践中,企业并行实施地域上分散的多个项目时,资源在各子项目之间的转移时间是影响多项目整体进度的关键因素,同时在动态多项目环境下,新项目不断到达且到达时间不可预知使得制定多项目调度计划遭遇更大困难。本文在动态环境下对资源转移时间型分布式多项目调度问题进行建模和求解,基于多代理系统建立分布式多项目调度问题的动态模型,并将拍卖理论引入其中,设计一种基于时间窗拍卖机制的分布式多代理系统(DMAS/ATW),在动态环境和资源转移时间约束下为多项目配置全局资源。通过一个具体的分布式多项目示例详细分析DMAS/ATW算法的动态调度过程,并基于MPSPLIB中的分布式多项目算例开展数值实验。实验结果表明：无资源转移时间约束时,DMAS/ATW算法求得的平均项目延迟同比相关文献中的DMAS/RIA算法最多减少42%,平均减少26%;有资源转移时间约束时,DMAS/ATW算法对1/3算例集的求解结果优于DMAS/RIA算法在无资源转移时间约束时的结果,验证了本文DMAS/ATW算法求解效果的优异性。对算例规模和全局资源利用系数的实验分析还表明,DMAS/ATW算法对不同规模和资源约束紧张程度的算例都具有良好的适应性。     

基于证据推理的不确定多属性决策方法

针对基本属性权重的不确定性,以及基本属性与广义属性评价集的不一致性等问题,提出一种基于证据推理的不确定多属性决策方法,将证据推理算法推广到更一般的决策环境中.根据决策矩阵的信息熵客观地获得属性的权系数;而对于基本属性与广义属性评价集不一致的情况,则通过对基本属性分布评价的模糊化及模糊变换,合理地实现到广义分布评价的统一形式;最后应用证据推理算法得到整个方案集的排序.实例结果表明,该方法是可行的、有效的.     

Stationary Equilibria in Asset‐Pricing Models with Incomplete Markets and Collateral

We consider an infinite‐horizon exchange economy with incomplete markets and collateral constraints. As in the two‐period model of Geanakoplos and Zame (2002), households can default on their liabilities at any time, and financial securities are only traded if the promises associated with these securities are backed by collateral. We examine an economy with a single perishable consumption good, where the only collateral available consists of productive assets. In this model, competitive equilibria always exist and we show that, under the assumption that all exogenous variables follow a Markov chain, there also exist stationary equilibria. These equilibria can be characterized by a mapping from the exogenous shock and the current distribution of financial wealth to prices and portfolio choices. We develop an algorithm to approximate this mapping numerically and discuss ways to implement the algorithm in practice. A computational example demonstrates the performance of the algorithm and shows some quantitative features of equilibria in a model with collateral and default.     

The optimal value range problem for the Interval (immune) Transportation Problem

We address the problem of finding the range of the optimal cost of a transportation problem when supply and demand vary over an interval. We consider the specific version of a transportation problem with supply inequality constraints and demand equality constraints under the assumption that the transportation costs are immune against the transportation paradox. We investigate some theoretical properties of the problem which constitute the basis of a novel solution algorithm. Our results show that the proposed algorithm hugely outperforms the best existing solution approaches.     

基于混合流水作业组织的集装箱码头装卸作业集成调度优化

集装箱码头集疏运资源调度的对象是由岸桥、集卡、场桥所构成的多阶段一体化的集装箱装、卸、运操作系统,将该系统的调度优化基于多阶段混合流水线调度问题建立混合整数规划模型,同时考虑集装箱码头现实作业中预定义顺序、避免岸桥交叉作业、以及取决于作业顺序的切换时间等现实约束,针对问题自身的特点设计了两阶段启发式算法,得出各阶段设备的指派结果及作业顺序。通过与基于现行调度规则的调度方案以及与目标函数理论下界值的对比实验,显示了所提出的集成调度模型及求解算法能够有效降低船舶在港时间并实现集卡资源的共享,为集装箱码头集疏运资源的集成调度提供了新的思路。     

LOCATION OF QUALITY INSPECTION STATIONS: AN EXPERIMENTAL ASSESSMENT OF FIVE NORMATIVE HEURISTICS

A number of heuristic decision rules have been proposed to aid in the location of quality inspection stations within a production line. Although these rules apparently enjoy an intuitive appeal, as yet no empirical investigation of their individual efficacies has been undertaken. This research identifies the relations between various cost and/or process characteristics and a designated “operative condition” that motivates the apparent rationale of five of these rules-of-thumb. Experimental results suggest that for several of the heuristics the operative condition was not associated with the performance of the rule. In addition, constraints in the processing environment were found to influence the effectiveness of the heuristics.