单台机器排序问题关于加工时间的反问题

本文研究单台机器总完工时间排序问题关于加工时间的反问题,研究尽量小地调整工件的加工时间使给定工件的加工次序成为最优的排序。我们考虑尽量小地调整是分别使最大带权相对离差的绝对值为最小、使总的带权相对离差的绝对值为最小或者使总的带权相对离差的平方为最小等三种情况。通过把问题转化成数学规划,我们分别指出这三种情况下的三个反问题都可以在多项式时间内求解。     

Scheduling a Single Machine to Minimize the Weighted Number of Tardy Jobs

In this paper the problem of scheduling jobs on a single machine to minimize the weighted number of tardy jobs is examined. It contains the framework for a new branch-and-bound procedure as well as the first extensive computational study of the problem. Results indicate that large problems, e.g. 50 jobs, can be solved in just a few seconds of computer time. Further, the computational results provide insight into how various problem parameters affect the solution difficulty of particular problems.     

Scheduling Jobs with Release Dates and Deadlines on a Batch Processing Machine

In this paper, we investigate the unbounded version of scheduling jobs with release dates and deadlines on a batch processing machine. NP-completeness is established for the case where all jobs have agreeable processing times and deadlines. Polynomial time algorithms are presented for the following cases: agreeable release dates and deadlines; agreeable release dates and processing times; a fixed number of distinct release dates, distinct processing times or distinct deadlines.     

考虑有限可用性可控的两批次并行机调度研究

构建了一个考虑有限可用性可控的两批次并行机调度模型.每台机器在考虑周期内可实施一次关机操作,由此形成一个不可用的时间段,关机开始时间和长度都不确定,需要在决策过程中决定,目标是最小化由完成时间和关机时间组成的总成本.先证明了问题最优解的一些性质,然后采用了基于列生成的分支定界法来求解,并结合了动态规划法来提高方法的效率...     

不确定环境下的单机成套订单鲁棒计划

讨论了不确定环境下订单数量可变的单机成套计划的优化问题,利用对偶变换给出了该问题的鲁棒整数规划模型,并设计了相应的遗传算法。算法对约束条件难点的处理采用了四种不同的方法即死亡惩罚、罚函数法、修补方法和解码方法,以检验算法的性能。最后进行了数值仿真实验,以比较不同算法的有效性。     

基于交货期的单机批量加工排序问题

针对钢铁、化工等工业的生产工件需分批、排序加工的特点,借助车辆路径问题的思想给出了制定批量单位的数学模型和基于禁忌搜索算法的求解方法,进一步讨论了这些批量单位在单机模式下,基于交货期的加工排序问题,给出了相应的优化模型和启发式算法。针对热轧生产进行数值仿真,取得了较为理想的成果。     

Minimizing Weighted Absolute Deviation in Single Machine Scheduling

This paper presents a procedure to minimize the total penalty when jobs are scheduled on a single machine subject to earliness and tardiness penalties. This performance criterion has been shown to be non-regular thus, requiring a search among schedules with inserted machine idle time to find a solution. A procedure to optimally insert idle time is also presented.     

总迟后相关的两个工况代理的单机排序问题

研究了两个代理的单机排序问题.其中一个代理以工件总迟后相关的为目标函数(总迟后和加权总迟后),第二个代理以最大费用函数为目标函数.排序问题的目标就是寻找一个序列,使得在第二个代理的目标函数不超过给定的上界的情况下,第一个代理的目标函数最小.对于总迟后的情形,并给出拟多项式时间的动态规划算法.当第一个代理中的工件具有相等工期时,考虑了加权总迟后问题,并给出了一个多项式时间算法.最后对于总迟后问题给数值实验.     

An Algorithm for a Single Machine Scheduling Problem with Sequence Dependent Setup Times and Scheduling Windows

An enumeration algorithm is presented for solving a scheduling problem similar to the single machine job shop problem with sequence dependent setup times. The scheduling problem differs from the job shop problem in two ways. First, its objective is to select an optimum subset of the available tasks to be performed during a fixed period of time. Secondly, each task scheduled is constrained to occur within its particular scheduling window. The algorithm is currently being used to develop typical observational timelines for a telescope that will be operated in earth orbit. Computational times associated with timeline development are presented.     

考虑急件到达的单机鲁棒调度方法

实际生产过程中经常会有急件到达。由于急件的优先级最高,其到达容易扰乱初始调度,使实际调度性能恶化,影响调度目标的实现。针对以总拖期为目标且带有释放时间的单机调度问题,研究了在有急件到达情况下的鲁棒调度方法,以降低急件对实际调度性能的影响。鉴于该调度问题是NP hard问题,根据工件释放时间和交货期的关系构造“金字塔”结构,获得该调度问题的占优性质。根据这些占优性质和急件到达特点,研究急件到达情景下的占优规则,据此求解急件到达情景下的占优调度集合,作为鲁棒调度的备选调度方案集合。提出了应对急件到达的鲁棒调度算法。给出仿真算例验证了算法的有效性,算例表明本文给出的鲁棒调度方法能有效避免急件到达造成实际调度性能的恶化。      

Optimization Models for Scheduling of Jobs

This work is motivated by a particular scheduling problem that is faced by logistics centers that perform aircraft maintenance and modification. Here we concentrate on a single facility (hangar) which is equipped with several work stations (bays). Specifically, a number of jobs have already been scheduled for processing at the facility; the starting times, durations, and work station assignments for these jobs are assumed to be known. We are interested in how best to schedule a number of new jobs that the facility will be processing in the near future. We first develop a mixed integer quadratic programming model (MIQP) for this problem. Since the exact solution of this MIQP formulation is time consuming, we develop a heuristic procedure, based on existing bin packing techniques. This heuristic is further enhanced by application of certain local optimality conditions.     

The Scheduling of Lots on a Single Facility

The problem of scheduling the production of lots of n products on a single facility is treated with the objective of minimizing the combined costs of setup, inventory, and backorder over a specified planning horizon. The discussion extends one of Elmaghraby's models (4) by developing a branch-and-bound algorithm which incorporates a dominance rule, a global precedence relation, and several local precedence relations.     

基于最优解下限的单工序平行机排序启发式算法

针对单工序平行机排序LPT方法计算步骤多等问题,提出了一种适用于中小企业现场排序的最优解下限截取启发式算法。传统平行机排序最优解下限表达式存在因偏离最优解过大而难以引导排序走向最优的缺陷,改进后的下限表达式更加接近于最优解。从计算步骤多少和偏离最优解下限的最大偏差率两个角度,比较分析了最优解下限截取法与LPT法的特点。经实验数据验证,得出零件数与平行机数之比非整除且满足一定条件时,简单易行的截取法更优于LPT法的结论。     

一类具有三重指标的分批排序问题

本文研究现代排序问题一具有三重指标的批容量无限制平行分批排序问题。第一指标为最大延迟,第二指标为最大完工时间,第三指标为关于工件完工时间的任意正规函数。本文通过分析前两个指标最优解的性质给出了此问题的多项式时间算法。     

Scheduling Production of Common Components at a Single Facility

We consider a model which deals with the fabrication of products at a single facility for later assembly into end products. Each product requires several part types: one unique part and others that are common to all the products. Also each production batch requires a setup. Baker provides a dynamic programming algorithm to determine a production schedule for minimizing the mean completion time for the case where each product requires only two part types: one unique and the other which is common to all products. In this paper we extend his analysis to our more general case.     

Scheduling a workforce under annualized hours

Annualized hours is a new idea in aggregate planning for seasonal businesses. Many manufacturing and services organizations in Europe have successfully used annualized hours to meet fluctuating demand. However, literature on scheduling a workforce under annualized hours is lacking. We fill this void by showing how to schedule workers over the year under a practical annualized hours scenario. The proposed scheduling algorithm is surprisingly simple.     

面向成套订单的生产与配送协调的排序研究

在工件体积和运输车辆容量的双重约束条件下,建立了以最大化成套订单数和最小化工件总配送时间的多目标规划模型,使用多目标排序寻找"约束解"的方法结合遗传算法求解此模型.最后通过算例分析,给出多目标规划模型及其综合算法在FLOW SHOP生产作业环境中的应用.计算结果表明,应用此模型和算法能够满足最大化成套订单数的要求,同时节省总的工件配送时间,有潜在的应用价值.     

Scheduling Production on One Machine with Changeover Costs

A single machine is used to produce several products so as to satisfy known demands over a fixed number of periods. Each time switches are made between products, there are changeover costs as described by a matrix C=[c_ij], where c_ij is the cost of switching from product i to product j. The problem is to find a schedule of production that minimizes the total changeover penalty while meeting the due dates of all customer orders. The function used in a forward-time dynamic program is shown to have a monotonicity property that can be used to advantage when seeking an optimal solution to the problem. This monotonicity property is applied in developing an efficient backward-time search procedure for solving the problem.     

单机带调整时间加权成套订单数问题遗传算法研究

通过大量的企业调研,提出了一类新的目标排序问题--单机带调整时间加权成套订单数排序问题:n个工件来自m个订单,分属B个不同类别,不同类之间的工件连续加工有调整时间,各工件有自己的交货期,一个订单中所有工件均按期完工则该订单成套完工,目标为加权成套延迟订单数最小.提出两类问题并且通过数学模型进行表述,设计相应的遗传算法,仿真结果表明该算法是可行而有效的.     

同时最优化时间表长与总完工时间的双代理单机序列分批排序问题（英）

本文研究在一台序列分批处理机上同时最优化$A$代理的时间表长和$B$代理的总完工时间的双代理排序问题．在序列分批的背景下,工件被分批加工（但不同代理的工件不能在同一批中加工,且每个代理都希望最小化仅依赖于各自工件完工时间的费用函数）且一批的加工时间等于这一批中所有工件的加工时间和．而且在一个新批开始加工前,机器有一个常数的安装时间．此外,根据批容量,序列分批模型又被分成有界模型和无界模型．在本文中,我们对所研究问题的有界模型和无界模型分别给出了一个多项式时间算法．