基于机动时间的可分解平行工序顺序优化研究

平行工序的顺序优化是解决资源有限项目进度计划问题的最有效、最普遍的方法之一。对于该类问题的研究目前主要基于工序的不可分解性,而现实情况下有些工序是任意可分的。基于此,本文首先提出了最小路长定理,在其基础上,建立了任意可分的两个平行工序调整为顺序工序的亏值模型,并进行了理论证明,此外,针对从n个可分解平行工序中选取一个与指定工序调整为顺序工序的优化问题进行了研究,在已给亏值模型的基础上设计出了优化算法,越是大型网络,该方法的优越性越明显。     

资源受限下平行工序顺序对优化的0-1规划模型

资源受限是工程项目时刻都可能面对的挑战。由于资源限制,需要将原项目计划中相互之间无优先关系的平行工序调整为顺序工序。平行工序顺序化可导致项目工期延迟,因此需考虑如何使项目工期延迟最小。该平行工序顺序优化问题是项目调度问题,也是排列组合问题,通常难度很大,包括一些NP-hard问题。本文主要研究该问题的一类典型子问题——平行工序顺序对优化,即如何将项目中某2n个平行工序调整为n个顺序工序对,并且对项目工期的影响最小。该问题的总方案数可达到（2n）!/n!。本文借助工序网络（如CPM网络）,运用简单的时间参数量化了平行工序顺序化对项目工期的影响,进而降低问题的求解难度,建立了纯0-1规划模型。实验验证了该模型的求解效率,求解100个平行工序规模的问题平均耗时0.2605秒,而求解500个平行工序规模的问题平均耗时10.66秒。     

一类Flow Shop排序问题的混合遗传算法

描述了在平行顺序移动方式下Flow Shop排序问题的数学模型，构造了求解该问题的混合遗传算法．用计算机模拟计算的结果表明，该算法对解决这类Flow Shop排序问题是有效的     

网络计划优化中资源平衡的混合遗传算法

目前网络计划优化的问题有两个第一,网络计划优化技术中的顺序优化没有统一的数学模型;第二,网络计划优化中的资源平衡的理念比较陈旧.资源平衡的混合遗传算法克服了过去的弱点,采用了合理的编码方法,建立了遗传算法的资源平衡模型,该算法首次考虑了资源日历,彻底解决了资源平衡与资源得不到的矛盾.     

二分群体决策规则的序性质研究

Karotkin等发现二分群体决策的加权多数决策规则集具有序性质,但未能解释其原因.文章提出了规则链和规则距离函数的概念,指出当一组决策规则构成规则链时这组规则便具有序性质,从而解释了这一现象.而判断一组规则是否构成规则链则可以通过计算各规则间的规则距离来实现.随后通过对具体实例的分析进一步阐述了得到的结论.     

集成电路板组装系统优化问题及其研究动态

集成电路组装是将电子元器件安装在集成电路板上,从而实现电子元器件的互联的过程,是电子信息行业的基础产业.本文将集成电路板组装系统优化问题划分为四个子问题组装顺序优化问题、部品指派优化问题、组装模式优化问题以及组装线平衡优化问题.重点介绍了其中的前三类子问题的优化模型及优化算法.并通过一个应用实例说明了模型及其算法的有效性.在此基础上,提出了今后对第四类子问题的研究方向与思路.     

《南开管理评论》来稿规范说明

1.本刊参考文献著录法只采用顺序编码著录法 顺序编码体系基本要求是:凡在正文中引述参考文献之处,务必在其右上角用方括号标注一阿拉伯数字序号,序号按自然数序编排,而在文后的“参考文献”中按此序码以规定格式著录文献的有关项目,参考文献与引文处的序码必须对应。     

供应链分销系统双层优化模型

分销渠道决策在整个供应链管理中非常关键,因为它直接影响着其它的市场决策. 从供 应链集成的角度出发,利用双层规划模型描述了二级分销网络优化问题,充分考虑了网络决策 部门及客户双方的自身及共同利益. 同时设计了启发式求解算法,最后用简单算例验证了模型 及其算法的有效性.     

《基础会计》模块化教学初探

教师授课一般是按课本顺序,由前向后顺序进行,很少考虑课程章节间的差异,采用分模块的、逆向的教学.会计学科因其特殊性,要求设计"顺逆结合"变序化的教学方法,分模块授课,以求实现教学的最优化.     

主从竞争链的纵向控制结构选择

针对链与链市场地位不平等情形,构建了2条具有先后决策顺序的主从竞争供应链模型,分析了不同纵向控制结构组合下主链先决策与从链后决策的供应链绩效和博弈均衡.研究发现,在主从链基于价格竞争条件下,2条链的博弈均衡为中心化控制结构.当2条链的市场规模悬殊时,随着竞争强度的增加,主链的利润逐渐降低,从链的利润逐渐增加.     

Parallel-machine scheduling of deteriorating jobs with potential machine disruptions

We consider parallel-machine scheduling of deteriorating jobs in a disruptive environment in which some of the machines will become unavailable due to potential disruptions. This means that a disruption to some of the machines may occur at a particular time, which will last for a period of time with a certain probability. If a job is disrupted during processing by a disrupted machine and it does not need (needs) to re-start after the machine becomes available again, it is called the resumable (non-resumable) case. By deteriorating jobs, we mean that the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging. However, a repaired machine will return to its original state of efficiency. We consider two cases, namely performing maintenance immediately on the disrupted machine when a disruption occurs and not performing machine maintenance. In each case, the objective is to determine the optimal schedule to minimize the expected total completion time of the jobs in both non-resumable and resumable cases. We determine the computational complexity status of various cases of the problem, and provide pseudo-polynomial-time solution algorithms and fully polynomial-time approximation schemes for them, if viable.     

Analysis of a batch machine fed by an unreliable discrete machine

This paper analyses the behaviour of a manufacturing line consisting of two machines in series where the first machine processes lots one at a time, and is subject to failure and takes a random amount of time to repair when it fails, and the second machine is a perfectly reliable batch machine. A control limit policy is adopted to determine lot sizes for the batch machine. When the batch machine completes processing, if the number of lots in the buffer is greater than or equal to the critical number (Q?), all the lots in the buffer are loaded immediately, otherwise the batch machine waits until Q lots are accumulated. An embedded discrete time Markov-chain approach is proposed, and recursive approaches are developed to derive necessary performance measures. A numerical example explains how to obtain the optimal value of a critical number minimizing the cost functions.     

Minimizing makespan in an ordered flow shop with?machine-dependent processing times

We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine. In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number of machines is fixed.     

Scheduling a single semi-continuous batching machine

This paper addresses a new problem, called semi-continuous batch scheduling, which arises in the heating-operation of tube-billets in the steel industry. Each heating furnace can be regarded as a semi-continuous batching machine, which can handle up to C jobs simultaneously. The jobs in the same batch enter and leave the machine semi-continuously, which differs from the traditional batching machine scheduling where the jobs in same batch have a starting time and a finishing time. In this paper the processing time of a batch depends on the capacity of the semi-continuous batching machine, the longest processing time of jobs in the batch and its size. The objectives are to schedule jobs on the machine so that the makespan and the total completion time are minimized. A schedule for a semi-continuous batching machine consists of a batching and sequencing for the batches. We propose the optimal properties of two different objective functions and present the different dynamic programming algorithms with a running time of O(n²), respectively.     

大规模集成电路预烧作业中分批排序问题的数学模型

分批排序(Batch Scheduling)是在半导体生产过程的最后阶段提炼出来的一类重要的排序问题。单机分批排序问题就是n个工件在一台机器上加工,要将工件分批,每批最多可以同时加工B个工件,每批的加工时间等于此批工件中的最大的加工时间。Skutella^[8]1998年把平行机排序的P｜｜∑ω_jC_j和R｜｜∑ω_jC_j表述成二次的0-1整数规划,得到一些令人满意的结果;国内罗守成等^[9]、张倩^[10]给出了单机排序问题1｜｜∑ω_jC_j的数学规划表示,对于用数学规划来研究排序问题是一个很有意义的进展。本文首先介绍总完工时间和最小的带权单机分批排序问题1｜B｜∑ω_jC_j,然后将1｜B｜∑ω_jC_j表示成数学规划的形式,并且用数学规划中的对偶理论证明了SPT序是其特殊情况1｜B=1｜∑C_j的最优解。     

Scheduling in an assembly-type production chain with batch transfer

This paper addresses a three-machine assembly-type flowshop scheduling problem, which frequently arises from manufacturing process management as well as from supply chain management. Machines one and two are arranged in parallel for producing component parts individually, and machine three is an assembly line arranged as the second stage of a flowshop for processing the component parts in batches. Whenever a batch is formed on the second-stage machine, a constant setup time is required. The objective is to minimize the makespan. In this study we establish the strong NP-hardness of the problem for the case where all the jobs have the same processing time on the second-stage machine. We then explore a useful property, based upon which a special case can be optimally solved in polynomial time. We also study several heuristic algorithms to generate quality approximate solutions for the general problem. Computational experiments are conducted to evaluate the effectiveness of the algorithms.     

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。     

无人零售业态下自动售卖机联合补货策略研究

研究无人零售业态下自动售卖机的多产品联合补货问题，建立由补货成本、库存持有成本、缺货成本构成的平均补货成本模型，分析容量约束与固定补货阈值下的最优补货策略。结果表明，企业会倾向于在剩余较少产品时进行补货，剩余的产品往往是投影面积最小使得相同面积可容纳最多数量的产品；比较最优补货时间与平均补货成本发现，延长补货时间可以降低平均补货成本，在补货阈值越大、固定补货成本越低或售卖机容量越小时，最优补货时间会降低，反之，平均补货成本会增加。此外，分析不同成本变动对平均成本的影响发现，单位成本变动均会引起平均补货成本的增加，且在单位库存持有成本变动时，最优补货策略会发生转移，向单位库存持有成本降低至一定程度的产品或向投影面积最低即相同面积可容纳数量最小的产品转移。     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.     

Scheduling with machine cost and rejection

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case, (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.