客户耐烦期相同的生产——库存系统最优模型

在常数需求率以及有限生产率条件下研究了订货客户耐烦期相同的一类新的生产——库存模型 ,在每一个周期内考虑了延期交货时间超过耐烦期的短缺费用和销售机会损失等因素 ,给出了相应的最优生产时间和周期的确定方法 ,利用数学软件 Matlab及计算机为工具给出了数字例子进行说明 ,其方法和结果为库存系统的管理决策提供了理论依据     

The Optimization of Paper Machine Scheduling

A method for determining schedules in a paper mill is described and applied to real production data. The problem is to allocate products to machines and determine their sequence so as to minimize total costs. The costs include production losses through set-ups, stock holding and penalties for delayed delivery. The method is based on a permutation representation of the production schedule and the determination of a locally optimal solution. A permutation is locally optimal if it cannot be improved by transferring groups of products to a different place in the schedule. The method has been programmed and the results show a considerable improvement over alternative manual procedures. The paper has been written in two parts, the first dealing with the development of the method and the second discussing its application to a specific problem.     

A modified tabu search algorithm for cost-based job shop problem

In this paper, a cost-based job shop problem (JIT-JSP) is proposed to model the multi-order processing procedure in a just-in-time (JIT) environment. The objective of JIT-JSP is to minimize three costs: work-in-process holding cost of half-finished orders, inventory holding cost of finished orders and backorder cost of unfulfilled orders. A modified tabu search (MTS) method is developed to improve the schedule quality by searching the neighbourhood of a feasible schedule iteratively. The MTS method is comprised of three components that help to ensure a more effective searching procedure: neighbourhood structure, memory structure and filter structure. Computational results show that the MTS method significantly improves the initial schedule generated by an arbitrarily selected dispatching rule.     

A hybrid genetic algorithm for the finite horizon economic lot and delivery scheduling in supply chains

In this paper, we investigate the lot and delivery scheduling problem in a simple supply chain where a single supplier produces multiple components on a flexible flow line (FFL) and delivers them directly to an assembly facility (AF). It is assumed that all of parameters such as demand rates for the components are deterministic and constant over a finite planning horizon. The main objective is to find a lot and delivery schedule that would minimize the average of holding, setup, and transportation costs per unit time for the supply chain. We develop a new mixed integer nonlinear program (MINLP) and an optimal enumeration method to solve the problem. Due to difficulty of obtaining the optimal solution in medium and large-scaled problems, a hybrid genetic algorithm (HGA) is also developed. The proposed HGA incorporates a neighborhood search (NS) into a basic genetic algorithm that enables the algorithm to perform genetic search over the subspace of local optima. The two proposed solution methods are compared on randomly generated problems, and computational results show that the performance of HGA is very promising because it is able to find an optimal or near-optimal solution for majority of the test problems.     

Balanced train timetabling on a single-line railway with optimized velocity

This paper aims to find an optimal balanced schedule with the least delay-ratio (i.e., the ratio of the total delay time and the total free-run time) by considering the impacts of the train velocity. A rigorous optimization model is proposed under the consideration of feasible speed constraint for finding the optimal velocity for each train on the railway line. To obtain an approximately optimal scheduling strategy, a combination of the improved TAS (ITAS) method and the genetic algorithm (GA), called GA-ITAS method, is in particular proposed to effectively solve the proposed model. The results of numerical experiments demonstrate the efficiency and effectiveness of the proposed approaches.     

An approach to optimize block surgical schedules

We provide an approach to optimize a block surgical schedule (BSS) that adheres to the block scheduling policy, using a new type of newsvendor-based model. We assume that strategic decisions assign a specialty to each Operating Room (OR) day and deal with BSS decisions that assign sub-specialties to time blocks, determining block duration as well as sequence in each OR each day with the objective of minimizing the sum of expected lateness and earliness costs. Our newsvendor approach prescribes the optimal duration of each block and the best permutation, obtained by solving the sequential newsvendor problem, determines the optimal block sequence. We obtain closed-form solutions for the case in which surgery durations follow the normal distribution. Furthermore, we give a closed-form solution for optimal block duration with no-shows.     

A hybrid scatter search heuristic for personalized crew rostering in the airline industry

The crew scheduling problem in the airline industry is extensively investigated in the operations research literature since efficient crew employment can drastically reduce operational costs of airline companies. Given the flight schedule of an airline company, crew scheduling is the process of assigning all necessary crew members in such a way that the airline is able to operate all its flights and constructing a roster line for each employee minimizing the corresponding overall cost for personnel. In this paper, we present a scatter search algorithm for the airline crew rostering problem. The objective is to assign a personalized roster to each crew member minimizing the overall operational costs while ensuring the social quality of the schedule. We combine different complementary meta-heuristic crew scheduling combination and improvement principles. Detailed computational experiments in a real-life problem environment are presented investigating all characteristics of the procedure. Moreover, we compare the proposed scatter search algorithm with optimal solutions obtained by an exact branch-and-price procedure and a steepest descent variable neighbourhood search.     

On a stochastic inventory model with a generalized holding costs

This paper is concerned with finding the optimal replenishment policy for an inventory model that minimizes the total expected discounted costs over an infinite planning horizon. The demand is assumed to be driven by a Brownian motion with drift and the holding costs (inventory and shortages) are assumed to take some general form. This generalizes the earlier work where holding costs were assumed linear. It turns out that problem of finding the optimal replenishment schedule reduces to the problem of solving a Quasi-Variational Inequality Problem (QVI). This QVI is then shown to lead to an (s, S) policy, where s and S are determined uniquely as a solution of some algebraic equations.     

Task scheduling with and without communication delays: A unified approach

The problem of scheduling directed acyclic task graphs on an unbounded number of processors is considered. We present a single algorithm which is applicable to several special cases, thus effecting a unified approach to task scheduling independent of the task graph. We start by considering multi-stage dags and present an algorithm that computes a schedule in O(Nq log q) time, where N is the number of stages, and q is the maximum number of edges between any two stages of the graph. We show that the schedule produced by the algorithm is optimal when: (i) all communication delays are zero or, (ii) the precedence graph is an in-tree or an out-tree and communication times are small or, (iii) the task graph is densely connected and communication costs and processing costs are unity. For multi-stage dags with small communication times we show that the makespan of the schedule generated by our algorithm is less than twice that of the optimal. We also bound the makespan for the case when communication times are arbitrary. We then show how the algorithm may be applied to schedule arbitrary dags and derive the performance bounds for this case. Finally, we present the results of tests we carried out with randomly generated task graphs. These seem to indicate that, on the average, the algorithm performs substantially better than theoretical worst case predictions.     

Transient and steady-state analysis of a manufacturing system with setup changes

This paper deals with the optimal scheduling of a one-machine two-product manufacturing system with setup, operating in a continuous time dynamic environment. The machine is reliable. A known constant setup time is incurred when switching over from a part to the other. Each part has specified constant processing time and constant demand rate, as well as an infinite supply of raw material. The problem is formulated as a production flow control problem. The objective is to minimize the sum of the backlog and inventory costs incurred over a finite planning horizon. The global optimal solution, expressed as an optimal feedback control law, provides the optimal production rate and setup switching epochs as a function of the state of the system (backlog and inventory levels). For the steady-state, the optimal cyclic schedule (Limit Cycle) is determined. This is equivalent to solving a one-machine two-product Lot Scheduling Problem. To solve the transient case, the system's state space is partitioned into mutually exclusive regions such that with each region is associated an optimal control policy. A novel algorithm (Direction Sweeping Algorithm) is developed to obtain the optimal state trajectory (optimal policy that minimizes the sum of inventory and backlog costs) for this last case.     

A production planning model for an unreliable production facility: Case of finite horizon and single demand

We study a two-level inventory system that is subject to failures and repairs. The objective is to minimize the expected total cost so as to determine the production plan for a single quantity demand. The expected total cost consists of the inventory carrying costs for finished and unfinished items, the backlog cost for not meeting the demand due-date, and the planning costs associated with the ordering schedule of unfinished items. The production plan consists of the optimal number of lot sizes, the optimal size for each lot, the optimal ordering schedule for unfinished items, and the optimal due-date to be assigned to the demand. To gain insight, we solve special cases and use their results to device an efficient solution approach for the main model. The models are solved to optimality and the solution is either obtained in closed form or through very efficient algorithms.     

基于控制工序性质的LOB截止日期问题分析与算法

截止日期问题是重复性项目调度中研究最为广泛的问题之一,其旨在满足项目截止日期前提下求得一个工作队雇佣总量最小的调度方案。由于重复性项目往往为大型工程建设项目,一个准确的最优进度计划对于节约项目的资源和成本具有重要意义。在平衡线法(LOB)框架下,本文从控制工序的性质出发,研究并分析了控制工序工作队分配与项目总工期之间的关联,给出了截止日期问题的一些特殊性质。基于这些性质,一方面能够帮助项目管理人员判断一个调度方案是否可行且经济,另一方面能够得到一些有效的剪枝策略,从而设计出具有针对性的分支限界算法。最后,通过案例计算和仿真实验验证了本文提出的算法在计算效果和计算效率上的有效性。     

Optimization of a highway project planning using a modified genetic algorithm

This paper proposes an optimization method for a national-level highway project planning based on a modified genetic algorithm. The proposed method adds to the existing methods by integrating various planning elements into a single system. A simulation model is used in order to determine the best investment strategy with regard to net present value, time deviation from the initial plan and discrepancy between available resources and investment costs by taking into account economical, social, traffic and political factors. The outcome is a project schedule with an optimized cash flow. The proposed method was tested using the example of the National Highway Programme in Slovenia.     

A Lagrangean heuristic algorithm for disassembly scheduling with capacity constraints

This paper considers the problem of determining the disassembly schedule (quantity and timing) of products in order to satisfy the demand of their parts or components over a finite planning horizon. The objective is to minimize the sum of set-up, disassembly operation, and inventory holding costs. As an extension of the uncapacitated versions of the problem, we consider the resource capacity restrictions over the planning horizon. An integer program is suggested to describe the problem mathematically, and to solve the problem, a heuristic is developed using a Lagrangean relaxation technique together with a method to find a good feasible solution while considering the trade-offs among different costs. The effectiveness of the algorithm is tested on a number of randomly generated problems and the test results show that the heuristic suggested in this paper can give near optimal solutions within a short amount of computation time.     

Demurrage costs optimization in ports using binary mathematical programming models

Summary SODA is a system by which the schedule of ships in a port can be found in order to minimize the demurrage and operating costs associated with shipping operations. SODA constructs and resolves binary programming models using shipping data (arrival dates, demurrage costs, berths to be used, etc.) and available berths in a planning horizon. The model is of an adjustable precision: major accuracy implies greater calculation time. SODA provides an optimal result to a complex problem in a resolution time which is generally better than that needed for a manual solution.     

A Cutting Stock and Scheduling Problem in the Copper Industry

This case study was carried out for Thomas Bolton Ltd, a copper component manufacturer. The focus was on the first major production operation that is carried out in the foundry. This operation consists of three processes — melting scrap metal, casting it as ‘logs’ and cutting logs into ‘billets’. The timely production of the billets is essential as these feed a bottleneck process. The objective of the study was to investigate alternative methods of generating a production plan for the foundry that minimized costs whilst meeting the demand for billets at the bottleneck. The production plan was required to include a daily production schedule and a list of the cutting patterns to use when cutting the logs into billets. Thus, both the scheduling and cutting stock problems were addressed. A two-stage solution procedure was proposed. Alternative heuristic methods were investigated at the first stage and an optimal solution using Integer Programming (IP) was proposed for the second stage. It is shown that current performance could be improved using all of the heuristics considered at the first stage, but that using an IP-based heuristic method gives the best results.     

Supply chain scheduling: Sequence coordination

A critical issue in supply chain management is coordinating the decisions made by decision makers at different stages, for example a supplier and one or several manufacturers. We model this issue by assuming that both the supplier and each manufacturer have an ideal schedule, determined by their own costs and constraints. An interchange cost is incurred by the supplier or a manufacturer whenever the relative order of two jobs in its actual schedule is different from that in its ideal schedule. An intermediate storage buffer is available to resequence the jobs between the two stages. We consider the problems of finding an optimal supplier's schedule, an optimal manufacturer's schedule, and optimal schedules for both. The objective functions we consider are the minimization of total interchange cost, and of total interchange plus buffer storage cost. We describe efficient algorithms for all the supplier's and manufacturers’ problems, as well as for a special case of the joint scheduling problem. The running time of these algorithms is polynomial in both the number of jobs and the number of manufacturers. Finally, we identify conditions under which cooperation between the supplier and a manufacturer reduces their total cost.     

考虑加工效率变化的变速机干扰管理研究

在变速机生产排序中, 受来自企业外部可改变机器加工效率的突发性干扰事件影响, 初始最小化企业生产成本的加工时间表不再最优,需要对其调整并在生产成本和干扰事件扰动之间进行权衡。建立了同时考虑生产成本和干扰事件扰动的重排序模型, 生产成本为所有机器的负载之和, 干扰事件的扰动为工件在不同机器之间重新安排所产生的运输费用和。设计了求解该重排序问题有效前沿的算法, 以及利用决策者对两个目标的偏好将双目标转化成一个二元非线性函数后, 求解优化该函数的有效解的算法。通过数值算例验证与整个有效前沿相比,优化二元函数的算法只需搜索部分有效前沿即可求出最优解,降低了有效解的搜索比例和运行时间,提高了干扰管理问题的处理效率。     

双机成比例无等待流水线重调度干扰管理研究

针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。