A Heuristic Production Lot Scheduling Model

This article describes a model which seeks to schedule the production of m products over the next n production planning periods in a manner which minimizes total setup, production, and inventory costs while observing all constraints imposed by the capacities of the productive resources. The model formulates this problem as a fixed charge problem, and then uses a modified version of the simplex method to locate optimal or near optimal solutions of this nonlinear programming problem. A discrete optimizing approach is used to estimate the effectiveness of the model.     

钢管冷区生产调度的一种启发式算法

基于国内大型钢铁公司的实际操作,运用离散化时间的方法把钢管冷区生产调度抽象为可中断Job-Shop问题.同时考虑前置库存限制、生产尽可能连续、部分人工调度等约束条件,以最小化中断次数和尽可能满足人工调度为目标,建立相应的数学模型.再依据约束条件的主次性设计生产调度规则(赋值规则和生产规则),根据实际生产流程设计启发式算法.运用该算法对该问题的大规模算例进行求解,其结果在满足了约束条件情况下达到比较理想的中断次数.     

一类多资源调度问题的优化算法

若调度系统中的作业或任务需要一个或多个资源共同完成， 则这一类调度问题被称为多资源（或多处理机）调度问题。本文针对Jobshop中的这一调度问题，提出了基于遗传的优化调度算法，并用实例证实了该算法的有效性。     

一类资源负荷均衡问题的优化调度算法

针对一类n个独立任务在m个不完全同等的处理机上处理，使处理机的最大负荷为最小的非抢先调度问题，提出了一种启发式算法－－最小平衡算法，并分析了它的时间复杂性，在此基础上，又将最小平衡算法和遗传算法结合起来，提出了基于遗传的最小平衡算法，并用实例证实了该算法的有效性。     

一类资源负荷均衡问题的双最小平衡调度算法

针对一类n个独立任务在m个不完全同等的处理机上处理，使处理机的最大负荷为最大的非抢先调度问题，在最小平衡算法的基础上提出了双最小平衡算法，并分析了它的时间复杂性，在此基础上，提出了基于遗传的双最小平衡算法，并通过实例证实了它在结果上优于基于遗传的最小平衡算法。     

Cutting Plane and Branch and Bound for Solving a Class of Scheduling Problems

Two general purpose integer programming algorithms, one a fractional cutting-plane algorithm and the other a branch-and-bound algorithm, were investigated. The cutting-plane algorithm easily solves an important class of integer problems, a class of scheduling problems for the assigning of personnel to work shifts over a fixed period of time. Scheduling problems were constructed with 14 to 189 integer variables and with 14 to 21 constraints. The general branch-and-bound search was not effective on this class of scheduling problems, but it was effective on the classical test problems found in the literature of integer programming, many of which were not handled by the cutting-plane algorithm.     

面向订单的生产计划与调度的综合优化

研究了一个多订单环境下的生产计划与调度集成优化问题,以实现准时生产为目标,综合考虑产品装配结构约束的订单任务计划与订单产品零部件的加工调度,采用直接面向客户订单的工序调度模式建立了计划和调度的综合优化整数规划模型.设计了带精英策略的蚁群算法作为该数学模型的求解方法,并通过对比试验为该算法选取最佳的搜索参数.实例仿真结果表明,所建模型的正确性以及蚁群算法求解该问题的可行性和有效性.     

An Algorithm for a Class of Three-Dimensional Assignment Problems Arising in Scheduling Applications

A scheduling problem often arising in trade shows and conventions is modeled as a planar three-dimensional assignment problem having a special cost structure. A polynomial-time algorithm for solving this case of the planar assignment problem is presented. The algorithm can also be used to solve heuristically a variation of the m-traveling salesman problem which arises as a secondary problem in the original scheduling application. Computational experience with data from a tourism industry convention scheduling problem is given.     

混合流程型企业主生产计划的启发式算法

提出了一个新的启发式算法,该启发式算法称为多目标主生产计划算法(MOMPS),用于解决混合流水线车间的主生产计划安排,该启发式算法主要有以下目标:最小化拖期惩罚,最小化完工时间,最小化装设和库存成本等.该算法先对所有的定单进行排序,然后根据最小生产成本树及其该树的最大生产能力进行定单的分配,如果定单数量超出了最大生产能力,对生产网络进行调整,通过比较次优生产成本树和拖期以后的最小生产成本决定定单是否该拖期.最后通过和一般的线性规划进行比较,得出该算法在解决混合流程型企业的多目标主生产计划的制定中十分有效,有时得到的结果和线性规划模型解出的解是一致的.     

Flexible Mixed-Integer Programming Formulations for Production Scheduling Problems

We present an approach to modeling practical dynamic production planning problems with product sequencing considerations that yields a significant reduction in the number of required binary variables over traditional approaches and improves the structure of special ordered sets which can be exploited in state-of-the-art mixed integer programming codes. In addition, the variable definition enables the modeler to develop a wide variety of objective functions, thus facilitating model development and interpretation.     

Evaluating a Modified Heuristic for the Multiple-Vehicle Scheduling Problem

This paper outlines a modified heuristic procedure for solving the multiple vehicle scheduling problem. The solution method alternates between a time saved heuristic and Little's Sequential Tour Building method [12]. The major impact of the heuristic procedure breaks the problem into feasible tours solving each of the tours with an optimizing procedure. To demonstrate how the modified heuristic works, a state wide bakery example was used. A comparison of the modified heuristic and two well known routing heuristics resulted in the selection of the modified heuristic as the method of choice. Given these preliminary results, a more complete testing of the heuristic and the well known Clark and Wright heuristic was performed. In this formal experiment both methods were modified to achieve route balance. The results indicated that the modified routing method showed an overall average improvement over the Clark and Wright heuristic. The results also showed a significant trade off between the number of customers and the mean savings between the two routing methods. The practical implications of the experimental results are promising. Vehicle schedulers facing scheduling situations where travel time (mileage) constraints are imposed can easily apply the modified procedure for manpower planning purposes.     

A Heuristic Procedure for Scheduling Packaging Lines in Process Industries

Process industries produce non-differentiable products which are packaged into a variety of sizes during the final production stage. In this environment, product family changeovers are performed during an off-shift period, while item changeovers, which are shorter in duration, may be performed during a shift. A heuristic for scheduling packaging lines is presented where a family setup cost is charged for an off-shift changeover and item lot sizes are determined subject to limited capacity and setup times.     

Integrated Production Planning and Scheduling on Automobile Assembly Lines

We address the closely related problems of production planning and scheduling on mixed model automobile assembly lines. We propose an integrated solution, in which a production plan that is feasible with respect to aggregate capacity constraints is developed and then a sequence that is feasible with respect to this plan is sought. We propose three tabu-search-based algorithms that explore the solution spaces for both problems to different degrees to find a combination of a production plan and schedule that are feasible and that approximately optimize the objective function (involving the overproduction and underproduction of finished automobiles, the set-up cost, the idle times of work-cells on the line, the makespan and the load deviations among work-cells). Simulation is used to evaluate alternative schedules. Stochastic extensions are proposed and the complexities of these algorithms are discussed. Example runs comparing the algorithms are presented for deterministic cases, stochastic cases, types of automobiles, buffer sizes and number of work-cells. The results show that an embedded tabu search algorithm is suitable for solving small scale problems, an alternate tabu search algorithm for the medium scale and a serial tabu search algorithm for the large scale.     

Heuristic Algorithms for Multistage Flowshop Scheduling Problem

This paper describes three heuristic algorithms for seeking a quick and near optimal solution to the n-job M-machine flowshop scheduling problem where jobs are processed on all machines in the same order, and the objective is to minimize either the mean flowtime or the maximum flowtime (make-span). The proposed heuristic algorithms are extensions of the heuristic rules of the author and are comparatively more effective in finding the optimal or near optimal solution to the problem. Computational experience pertaining to the effectiveness of proposed heuristic algorithms is discussed, indicating that the solutions obtained by proposed heuristic algorithms are compared to the Campbell-Dudek-Smith algorithm.     

Heuristic Scheduling for Cyclic Steam Injection Projects

This article presents a well steam injection scheduling model which attempts to maximize the profit per day for oil production leases. The model consists of nonlinear regression, nonlinear optimization and a scheduling algorithm. Weekly well production data from a production reporting system is utilized to extend the system to a reporting, operating control and planning system. Thus, it not only provides management with production history but analysis tools for better decisions as well.     

集成预防性维护计划的单机调度蚁群优化研究

尽管生产调度与预防性维护计划密切相关,且其共有目标都是提高机床的利用率,但是存在着调度优化上的冲突.为了综合考虑单机情形下的生产调度与预防性维护计划,提出了一种改进的蚁群优化算法,用于解决以总计作业加权完成时间和总计维护成本最小为双目标的生产调度与预防性维护计划的集成模型.同时进行了大量的仿真实验,比较结果表明提出的蚁...     

On Equivalent Transportation Models for Production Planning Problems

In this note we show how to generalize Klein's observation that certain production planning problems can be modeled as transportation problems. This represents an application of an old result due to Wagner and described in Ford and Fulkerson's book.     

平行机系统生产调度与维护计划联合优化

针对平行机系统中生产调度和维护计划的联合决策问题,假设随机故障服从威布尔分布,将作业在设备上加工位置以及设备上预防性维护位置作为决策变量,以最小化最大完工时间和最小化单位维护成本作为优化目标建立了多目标优化模型.建立了基于混合编码的遗传算法,针对不同编码类型采用合适的遗传算子,并引入了自适应交叉和变异概率使算法在收敛速度和求解精度上得到较好平衡.通过与枚举算法对比,证明遗传算法具有较好的时间效率和求解精度.通过与独立决策模型对比,证明联合优化模型能更好地解决联合优化问题,提高企业整体效益.     

Column Generation Based Heuristic Algorithm for Multi-Item Scheduling

The column generation algorithm for the multi-item lot-size scheduling problem under resource constraints is examined and improved upon by augmenting simpler heuristic routines in place of the time-consuming Wagner-Whitin dynamic programming routine. The heuristic algorithms thus developed are tested by controlling problem size, setup time, demand variability, and capacity change costs in test problems. The empirical results indicate that the proposed heuristic algorithms reduce CPU time as well as the number of iterations with only a slight loss in optimality.