单油罐修理线的天车运送周期性排序问题的求解

作为机车油罐修理中的一个重要资源,天车的排序直接影响系统的生产率.本文研究了产品在系统的一边装载、而在另一边卸载的油罐单修理线的天车周期性排序问题.工件在每个工作台需要加工一定的时间,工作台之间没有缓冲工作台,一台天车用于工作站之间工件的运送,目标是对运送进行排序以极小化生产周期.为了求解这个问题,本文提出了一个混合整数线性规划模型,量化示例表明所提出的方法是有效的.     

两台单机的合作排序问题北大核心CSCD

本文研究下面情形的排序问题,两个代理商联合加工来自客户的一个工件集,每个代理商仅有一台单机用于加工工件,每个工件仅需被其中的一台单机无中断地加工一次.在完成分配工件的加工任务后,每个代理商将获得一定的收益并付出一定的加工费用.需要找出工件集的一个最优划分,使得两个代理商的净收益乘积最大.本文研究三个不同经典排序目标作为加工费用的两机合作排序模型,证明模型复杂性,分析最优解结构并设计动态规划算法.     

两台单机的合作排序问题

本文研究下面情形的排序问题,两个代理商联合加工来自客户的一个工件集,每个代理商仅有一台单机用于加工工件,每个工件仅需被其中的一台单机无中断地加工一次.在完成分配工件的加工任务后,每个代理商将获得一定的收益并付出一定的加工费用.需要找出工件集的一个最优划分,使得两个代理商的净收益乘积最大.本文研究三个不同经典排序目标作为加工费用的两机合作排序模型,证明模型复杂性,分析最优解结构并设计动态规划算法.     

工件具有子工件工期的排序问题

研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成,每个子工件都有各自的工期.只有当工件的每个子工件都按时完成,才能称该工件是按时完工工件,否则,称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时,该问题是NP-难的,而且不存在完全多项式时间近似方案(fully polynomial time approximation scheme,简记为FPTAS).提出两个启发式算法,利用数值模拟比较它们的性能,并且将这两个启发式算法的解与最优解的上界进行比较.     

加工时间离散可控的分批配送排序问题

研究了工件的加工时间是离散可控的,并且工件加工完后需要分批配送到客户的单机排序问题.一个客户在初始时刻将一批工件交给一个制造商进行加工.每个工件有多种加工模式,分配给每个工件的加工资源越多,则其加工时间越短.工件生产完后需要分批配送到客户处,每一批需要花费一定的时间和费用.研究了排序理论中主要的四个目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对具体的问题给出了它们的最优算法.     

具有优先约束的单机随机排序问题

讨论工件的加工时间为常数,机器发生随机故障的单机随机排序问题,目标函数极小化工件的加权完工时间和的数学期望最小.考虑两类优先约束模型.在第一类模型中,设工件间的约束为串并有向图.证明了模块M的ρ因子最大初始集合I中的工件优先于模块中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到机器发生随机故障的情况.在第二类模型中,设工件间的约束为出树优先约束.证明了最大家庭树中的工件优先于家庭树中其它的工件加工,并且其工件连续加工所得到的排序为最优排序并给出了最优算法.     

CIMS缓冲区分配工件的阈值控制策略及其优化

本文对两个并行不同的工作站，在有限的缓冲区中，提出了一类分配工件的阈值控制策略．首先利用结构矩阵分析理论，在这类阈值控制策略下给出了这个CIMS可靠性模型的随机结构，得到了系统的稳态生产率和稳态可用度，推导了这类阈位控制策略的两类持续时间的分布，然后在保证系统稳态生产率最大的目标下，得到了这类阈值控制策略的PW－最优解和PT－最优解．     

带可分配工期的总误工问题的应急管理

本文考虑了单机排序中带可分配工期的总误工问题的应急管理问题.针对不同情况建立不同的模型,利用交换和动态规划的方法,得到了每个模型的最优解或近似解.     

工件延误和可拒绝下的单机重新排序问题的近似方案

研究工件延误产生干扰且延误工件可拒绝下的单机重新排序问题.在该问题中,给定计划在零时刻到达的一个工件集需在一台机器上加工,工件集中的每个工件有它的加工时间和权重,在工件正式开始加工前,按照最短赋权加工时间优先的初始排序已经给定,目标函数是极小化赋权完工时间和,据此每个工件的承诺交付截止时间也给定.然而,在工件正式开始加...     

单机排序中关于完工前总损失的应急管理

该文研究了扰动环境下的关于完工前总损失的单机排序问题, 也就是这样一个问题: 在时刻 t , 一部分工件已经完工了, 一个扰动发生了, 在这种情形下, 原来的排序已经不是最优排序甚至是不可行排序了. 因此就需要对未完成的工件找一个新的排序. 作者采用的方法与大多数重新排序问题所不同的是: 模型里包含了原始排序与新排序之间的偏差所造成的损失. 作者主要研究了在原始排序中加权最短加工时间规则(WSPT)是最优排序的情形. 根据扰动的类型, 应急管理策略的类型以及目标函数, 研究了几个问题. 对于每个问题, 作者找到了最优排序或者得出了一些重要结果.     

A solution for cyclic scheduling of multi-hoists without overlapping

In this paper, we study the cyclic scheduling problem for electroplating lines where products are loaded into the system at one end and unloaded at the other end. The electroplating jobs must be processed within a given time window in each tank. There is no buffer between tanks. Two hoists sharing a common track are used to move products between the tanks in the production line. The objective is to minimize the production cycle time through scheduling hoist moves. A solution procedure is proposed in this study. The production line is first divided into two non-overlapping zones with a hoist assigned to each zone. Then a mixed integer linear programming model is developed for scheduling hoist moves. Computational results on a benchmark example problem are given in the paper to demonstrate the application of the proposed method.     

An Evolutionary Approach for the Design and Scheduling of Electroplating Facilities

This paper tackles the Cyclic Hoists Scheduling Problem. This problem is often encountered in electroplating facilities when mass production is required. Then a repetitive sequence of moves is searched for the hoists. We more precisely deal with a global optimization problem that simultaneously considers the design and the scheduling of such production lines. It consists in studying systems integrating several transportation resources, called hoists, by minimizing the cycle time, while minimizing the number of hoists used. To achieve these goals, we use an evolutionary approach. The encoding of one solution is based on the representation of the empty moves of the hoists. To evaluate each individual, we propose a linear programming model. This one both verifies the satisfaction of constraints and provides the best cycle time for the considered number of hoists. This contribution describes a promising approach to solving a simple version of this problem, namely cyclic hoist scheduling, based on Evolutionary Algorithms (EAs), which is an optimization method inspired by biological evolution models. The issues of solution encoding and specialised genetic operators with a repair procedure of the infeasible solutions are discussed. Some results are presented with benchmark examples.      

Inferring an ELECTRE TRI Model from Assignment Examples

Given a finite set of alternatives, the sorting problem consists in the assignment of each alternative to one of the pre-defined categories. In this paper, we are interested in multiple criteria sorting problems and, more precisely, in the existing method ELECTRE TRI. This method requires the elicitation of parameters (weights, thresholds, category limits,...) in order to construct the Decision Maker's (DM) preference model. A direct elicitation of these parameters being rather difficult, we proceed to solve this problem in a way that requires from the DM much less cognitive effort. We elicit these parameters indirectly using holistic information given by the DM through assignment examples. We propose an interactive approach that infers the parameters of an ELECTRE TRI model from assignment examples. The determination of an ELECTRE TRI model that best restitutes the assignment examples is formulated through an optimization problem. The interactive aspect of this approach lies in the possibility given to the DM to revise his/her assignment examples and/or to give additional information before the optimization phase restarts.     

An interactive sorting approach based on the assignment examples of multiple decision makers with different priorities

Although group decision-making is often adopted by many organizations in today??s highly complicated business environment, the multiple criteria sorting (MCS) problem in the context of group decision-making has not been studied sufficiently. To this end, we propose a new interactive method to assist a group of decision makers (DMs) with different priorities. With the goal of relieving the cognitive effort exerted by DMs, this method uses the assignment examples provided by the DMs to draw the parameters for the group preference model. In the iterative MCS process that we employ, the DMs are supported from two perspectives. When the assignment examples provided by the DMs are inconsistent, a RINCON algorithm is developed to identify all the possible solutions that the DMs can use to resolve the conflicts. When the examples are consistent, the potential and the fittest assignments of each alternative are deduced using linear programming techniques. These are then presented to the DMs to help them provide more information for the decision-making process. Furthermore, the priority of each DM is objectively and subjectively evaluated, and then progressively updated to reflect the decision-making performance of a DM at each iteration. Meanwhile, the priorities are integrated into the linear programming model to deduce the fittest assignment, as well as into the RINCON algorithm. Hence, the assignment examples of the DMs with higher priorities are emphasized in the fittest assignment, and are less likely to be revised for inconsistency. A practical example featuring MBA programs is also presented to demonstrate the proposed method.     

Optimal workforce assignment to operations of a paced assembly line

We study a paced assembly line intended for manufacturing different products. Workers with identical skills perform non-preemptable operations whose assignment to stations is known. Operations assigned to the same station are executed sequentially, and they should follow the given precedence relations. Operations assigned to different stations can be performed in parallel. The operation’s processing time depends on the number of workers performing this operation. The problem consists in assigning workers to operations such that the maximal number of workers employed simultaneously in the assembly line is minimized, the line cycle time is not exceeded and the box constraints specifying the possible number of workers for each operation are not violated. We show that the general problem is NP-hard in the strong sense, develop conventional and randomized heuristics, propose a reduction to a series of feasibility problems, present a MILP model for the feasibility problem, show relation of the feasibility problem to multi-mode project scheduling and multiprocessor scheduling, establish computational complexity of several special cases based on this relation and provide computer experiments with real and simulated data.     

有资格限制的指派问题的求解方法

在实际的指派工作中，常会遇到某个人有没有资格去承担某项工作的问题，因此，本建立了有资格限制的指派问题的数学模型。在此数学模型中，将效益矩阵转化为判定矩阵，由此给出了判定此种指派问题是否有解的方法；在有解的情况下，进一步将效益矩阵转化为求解矩阵，从而将有资格限制的指派问题化为传统的指派问题来求解。最后给出了一个数值例子来说明这样的处理方法是有效的。     

一类广义指派问题的有效解法

提出一类广义指派问题,这类问题研究的是m个人执行n项任务,每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制,要求最优指派.对这类广义指派问题建立了数学模型,并找到一种转换方法,将这类问题转换为平衡指派问题,从而用传统方法,如匈牙利法求解.最后用一个箅例来说明这种转换方法的简便和有效性.     

A genetic algorithm for robotic assembly line balancing

Flexibility and automation in assembly lines can be achieved by the use of robots. The robotic assembly line balancing (RALB) problem is defined for robotic assembly line, where different robots may be assigned to the assembly tasks, and each robot needs different assembly times to perform a given task, because of its capabilities and specialization. The solution to the RALB problem includes an attempt for optimal assignment of robots to line stations and a balanced distribution of work between different stations. It aims at maximizing the production rate of the line. A genetic algorithm (GA) is used to find a solution to this problem. Two different procedures for adapting the GA to the RALB problem, by assigning robots with different capabilities to workstations are introduced: a recursive assignment procedure and a consecutive assignment procedure. The results of the GA are improved by a local optimization (hill climbing) work-piece exchange procedure. Tests conducted on a set of randomly generated problems, show that the Consecutive Assignment procedure achieves, in general, better solution quality (measured by average cycle time). Further tests are conducted to determine the best combination of parameters for the GA procedure. Comparison of the GA algorithm results with a truncated Branch and Bound algorithm for the RALB problem, demonstrates that the GA gives consistently better results.     

基于优势的双边匹配决策方法

传统的双边匹配方法根据主体双方给出的偏好序信息排序, 忽略匹配双方个体间存在的差异, 匹配结果不能很好的满足主体需求, 稳定性较差, 造成资源的错配甚至浪费。本文以人为出发点, 基于对匹配主体特征属性的优势结构识别, 提出新的序值依据, 将定性的不确定匹配标准依重视程度量化, 从而实现对人的多维度测量, 最大化个体差异, 以实现“按需匹配”的高稳定性、高满意度匹配结果。构建基于主体客观评价的优势属性量表; 引入个体综合情况的计算公式; 依托隶属度加权法把多目标优化转变成单目标优化; 运用Hungarain方法获得满意度最高且稳定匹配的指派方案; 最后通过算例证明本方法的科学性和可行性。     

Modelling and solving the production rate variation problem (PRVP)

Several families of objective functions for the PRV problem (minimizing the variation in the rate at which different products are produced on an assembly line) are formalized, relationships between them are established and it is demonstrated that, in very general conditions, they can be optimized by solving an assignment problem or a polynomially bounded sequence of assignment problems.