基于遗传禁忌算法考虑转运约束的并行机批量调度问题研究

在多品种混流生产车间里，广泛存在着各种批量的任务在多台并行机上调度优化问题。这种并行机批量调度需要考虑批量大小设置、加工顺序优化、设备充分利用等多种要素，是一类典型NP-hard问题，且当任务加工完后还需要考虑转运过程时，问题将变得更加复杂。为了减少并行机生产过程中任务拖期和在制品积压，寻求更好的生产调度方案，针对典型并行机生产和转运场景，以最小化加权完工时间及拖期工件的惩罚费用、作业切换成本、库存成本之和为优化目标，设计了基于启发式规则的仿真程序与遗传禁忌算法相结合的优化算法，研究单工序不相关并行机调度环境下车间批量调度的最优调度方案，再通过案例验证了本文优化算法的有效性。结果表明，优化算法得出的并行机批量调度方案使得作业切换次数和拖期订单大大减少，减少在制品库存的同时提高了转运资源的利用率。     

供应链管理中提前期影响因素分析

提前期是供应链管理中的一个重要参数。它对于基于时间段的供应链的计划开始时间和计划数量、库存控制策略、批量等都有直接的影响，分析了在供应链管理中提前期对采购件、制造件的影响因素，提出了缩短提前期的思路。     

生产进度的同步化方法研究

传统的生产进度计划方法假设生产能力是平衡的,生产提前时间和经济生产批量是确定的,以之有基础制定的生产进度计划不能反映现实的生产状况,实际的生产经常不能按预定的进度完成,根据同步生产的思想和约束管理的原则,提出一种生产进度的同步化方法,该方法可应用在各种类型的制造企业中。     

客户化供应链中自制件动态提前期的一种计算方法

提前期是供应链管理中的一个重要参数,它对于基于时间段的供应链的计划开始时间和计划数量、库存控制策略、批量等都有直接的影响。本文介绍了客户化大量生产的概念与供应链管理的思想,描述了客户化供应链的形成和特点。在对供应链提前期分析的基础上,提出了一种自制件动态提前期的计算方法作为对供应链固定提前期的补充,以提高供应链系统的运行效果。     

多层级装配作业车间分批调度算法设计与分析

多层级装配作业车间调度是一类包含加工与装配的双阶段调度问题，装配产品具有不同的树状结构，且各层级的装配工序需要直属零部件完工方可执行。分批调度可以提高车间生产流动性，故而被运用在作业车间调度等领域。装配作业车间分批调度需要解决关联零部件及其下属子批的进度协同性问题，为此建立了多层级装配作业车间的分批优化调度模型，以最小化拖期成本与库存持有成本为优化目标。出于求解效率考虑，构建基于遗传算法与优先分派规则的混合求解算法以应对批量划分与排序两个子问题。最后，设计仿真实验验证分批调度算法的有效性，并分析评估在8种作业分派规则、3类分批策略下混合算法对于差异化产品结构的适应性。通过分析实验结果发现，等量分批策略可以在给定条件下有效提升混合算法的调度性能。     

一个小批量多品种的生产计划模型

用线性目标规划方法构造了一个小批量多品种企业产生管理系统的年度生产计划模型，结合工厂实际提出了在物料需求计划中计算提前期的经验公式，最后则用AHP方法确定了作业计划中的零件优先加工系数。     

对系统提前期/等待时间敏感的批量排队优化模型

过长的制造提前期和过高的在制品库存等问题造成Job shop的生产系统瓶颈,传统的批量策略没有考虑到这些因素.分析了产能、WIP、平均等待时间、系统制造提前期等参数对批量决策的影响,提出了两种不同批量优化策略,分别是减少平均等待时间的最优批量策略和缩短制造提前期的最优批量策略.参数敏感性分析表明,产能约束下,这两种批量...     

考虑订单合批批量的在线制造商承诺交货期决策研究

承诺交货期策略即向所有顾客承诺一致的交货时间是在线制造商最常用的基于时间的竞争策略。制造商通过调整运营参数来改变交货时间以实现向顾客承诺的交货期。基于运营批量对生产提前期的影响,本文构建了考虑订单合批批量的承诺交货期决策模型,分析了各种参数对生产提前期与运输提前期决策的影响。研究表明,库存成本、单位产品的加工时间、顾客需求的价格敏感性和时间敏感性系数等参数对于在线制造商的生产提前期和运输提前期决策往往具有不同的影响。最后本文的算例验证了研究的结论。     

优化交货可靠性的装配作业车间分批调度

装配作业车间生产多规格小批量装配型产品,通常具有差异BOM结构,主要由客制零件组成,但同规格产品仍然包含一定比例的可互用零件,每类零件具有一定批量。此类车间分批调度需要最优化零件类的批次分割和子批加工序列。考虑客户对高交货可靠性的需求,构建了基于最优化交货可靠性为决策优化目标的分批调度数学模型,建立了基于遗传算法和优先级分派规则的混合求解算法。最后通过仿真实验分析和验证了所提方法的有效性。     

采购与多层生产计划问题的协同优化

针对生产与采购这两项企业的重要活动,建立了一种采购计划和多层生产计划的集成优化模型,将采购计划、批量计划以及作业排序这三层计划问题进行综合决策。为求解该问题,设计了一种遗传算法和网络优化方法相结合的协同优化策略,遗传算法中每一个个体同时包含了批量计划和作业排序,并调用网络优化模型得出订购策略。数值仿真实验显示了提出的方法求解该类集成优化问题的良好性能。通过与独立优化方法进行比较,显示了协同优化策略的优越性。     

A batch splitting method for a job shop scheduling problem in an MRP environment

The job shop scheduling problem has been a major target for many researchers. Unfortunately though, most of the previous research was based on assumptions that are different from the real manufacturing environment. Among those distorted assumptions, two assumptions about set-up time and job composition can greatly influence the performance of a schedule. First, most of the past studies ignored the impact of the before-arrival set-up time. If we know the sequence of operations in advance, we can obtain an improved schedule by preparing the setup before a job arrives. Secondly, most of the past studies assumed that a job consists of only a single part, that is a batch of size one. However, if we assume that a job consists of a batch size greater than one, as in many real manufacturing environments, then we can obtain an improved schedule because we can fill up the idle times of machines with jobs which have smaller processing times by splitting the original batches. However, the number of job orders may then increase due to the split, and the size of the scheduling problem would become too large to be solved in a practical time limit. Consequently, there may be an optimum batch size considering trade-off between better solution and tractability. The current study is the result of an attempt to find an acceptable solution when the production requirement from a MRP system for a planning period exceeds the capacity of a production system. We try to get an improved schedule by splitting the original batch into smaller batches, and consider setting up a machine before the actual arrival of jobs to that machine. Thereby we can meet the due date requirement without resorting to rescheduling of the master production schedule. For the given batch, we disaggregate it according to the algorithm we are proposing. A so-called 'modified shifting bottleneck procedure' is then applied to solve the job shop scheduling problem with a before-arrival family set-up time considering release date, transportation time and due date. The study also shows that we can adapt to unexpected dynamic events more elegantly by allowing the splitting of batches.     

Choices in manufacturing strategy decision areas in batch production system – six case studies

The configuration of a production system can be described by the choices a firm makes in its manufacturing decision areas. Manufacturing strategy literature lacks empirical research in manufacturing decision areas. The current paper is an exploratory study using six case companies on alternative configurations that can exist in a batch production system. Choices made in decisions such as layout, shop floor control, etc., were found to be similar for all six companies that use batch process. However, there were a number of decisions that were found to be non-process specific and are influenced by product complexity, important competitive priorities, strategic orientation of manufacturing, top management decisions and the size of the company. The paper concludes with managerial implications and future research directions.     

Batch versus cyclic scheduling of flexible flow shops by mixed-integer programming

New mixed-integer programming models are proposed for deterministic batch or cyclic scheduling in flow shops with parallel machines and finite in-process buffers. Models for scheduling with all machines continuously available for processing throughout the entire scheduling horizon as well as for scheduling with an arbitrary pattern of machine availability due to pre-scheduled downtime events are provided. Numerical examples modelled after real-world flexible flow shop scheduling in electronics manufacturing are presented, and to compare the batch and cyclic schedules with continuous or with limited machine availability, results of computational experiments are reported.     

Minimising makespan on parallel batch processing machines with non-identical ready time and arbitrary job sizes

This paper considers the parallel batch processing machine scheduling problem which involves the constraints of unequal ready times, non-identical job sizes, and batch dependent processing times in order to sequence batches on identical parallel batch processing machines with capacity restrictions. This scheduling problem is a practical generalisation of the classical parallel batch processing machine scheduling problem, which has many real-world applications, particularly, in the aging test operation of the module assembly stage in the manufacture of thin film transistor liquid crystal displays (TFT-LCD). The objective of this paper is to seek a schedule with a minimum total completion time for the parallel batch processing machine scheduling problem. A mixed integer linear programming (MILP) model is proposed to optimise the scheduling problem. In addition, to solve the MILP model more efficiently, an effective compound algorithm is proposed to determine the number of batches and to apply this number as one parameter in the MILP model in order to reduce the complexity of the problem. Finally, three efficient heuristic algorithms for solving the large-scale parallel batch processing machine scheduling problem are also provided.     

Dynamic scheduling of batch servers with compatible product families

Dynamic scheduling is considered for batch processing machines. Research is motivated by the burn-in ovens found in semiconductor manufacturing. So far, research in this field has concentrated on control strategies that assume batches to be homogeneous, i.e. products should all belong to the same family. However, burn-in ovens may allow simultaneous processing of alternative families of products. Each family may set different requirements to processing times. The processing time of a batch is equal to the longest processing time required among all products in the batch. A new scheduling approach is proposed that addresses these situations. The objective is to minimize average flow time per product for the batch operation. The so-called look-ahead strategy adapts its scheduling decision to shop status, which includes information on a limited number of near future arrivals. The potential of the new strategy is demonstrated by an extensive simulation study.     

Adaptive scheduling of batch servers in flow shops

Batch servicing is a common way of benefiting from economies of scale in manufacturing operations. Good examples of production systems that allow for batch processing are ovens found in the aircraft industry and in semiconductor manufacturing. In this paper we study the issue of dynamic scheduling of such systems within the context of multi-stage flow shops. So far, a great deal of research has concentrated on the development of control strategies, which only address the batch stage. This paper proposes an integral scheduling approach that also includes succeeding stages. In this way, we aim for shop optimization, instead of optimizing performance for a single stage. Our so-called look-ahead strategy adapts its scheduling decision to shop status, which includes information on a limited number of near-future arrivals. In particular, we study a two-stage flow shop, in which the batch stage is succeeded by a serial stage. The serial stage may be realized by a single machine or by parallel machines. Through an extensive simulation study it is demonstrated how shop performance can be improved by the proposed strategy relative to existing strategies.     

Route selection and flow control in a multi-stage manufacturing system with heterogeneous machines within stages

With increasing market competition and the need to serve diverse market segments, many companies are responding to customer needs by manufacturing parts in small batches. Unless properly planned, batch production can lead to high material handling time. In this paper, a methodology for selecting the best routeing for a batch in a multi-stage production system with material handling considerations is presented. Each stage consists of multiple, functionally identical machines that have non-identical characteristics. The model determines the optimal routeing for the batch and generates the number of parts to handle or transport at a time as a unit load between machines in order to minimize total batch manufacturing time. The result from the model provides the optimal routeing (i.e., the machine to use at each production stage) and the number of parts to move at a time as a sub-lot. The solution procedure developed is easy to use and can be incorporated as a daily shop management tool.     

Scheduling a no-wait flow shop containing unbounded batching machines

We study the problem of scheduling n jobs in a no-wait flow shop consisting of m batching machines. Each job has to be processed by all the machines. All jobs visit the machines in the same order. A job completed on an upstream machine should be immediately transferred to the downstream machine. Batching machines can process several jobs simultaneously in a batch so that all jobs of the same batch start and complete together. The processing time of a batch is equal to the maximum processing time of the jobs in this batch. We assume that the capacity of any batch is unbounded. The problem is to find an optimal batch schedule such that the maximum job completion time, that is the makespan, is minimized. For m = 2, we prove that there exists an optimal schedule with at most two batches and construct such a schedule in O(n log n) time. For m = 3, we prove that the number of batches can be limited to nine and give an example where all optimal schedules have seven batches. Furthermore, we prove that the best schedules with at most one, two and three batches are 3-, 2- and 3/2-approximate solutions, respectively. The first two bounds are tight for corresponding schedules. Finally, we suggest an assignment method that solves the problem with m machines and at most r batches in O(n^{m(r-2)+1+[m/r]}) time, if m and r are fixed. The method can be generalized to minimize an arbitrary maximum cost or total cost objective function.     

A hybrid differential evolution algorithm for a two-stage flow shop on batch processing machines with arbitrary release times and blocking

Batch processing machines (BPMs) have important applications in a variety of industrial systems. This paper considers the problem of scheduling two BPMs in a flow shop with arbitrary release times and blocking such that the makespan is minimised. The problem is formulated as a mixed integer programming model. Subsequently, a hybrid discrete differential evolution (HDDE) algorithm is proposed. In the algorithm, individuals in the population are first represented as discrete job sequences, and mutation and crossover operators are applied based on the representation. Second, after using the first-fit rule to form batches, a novel least idle/blocking time heuristic is developed to schedule the batches in the flow shop. Furthermore, an effective local search technique is embedded in the algorithm to enhance the exploitation ability. The performance of the proposed algorithm is evaluated by comparing its results to a commercial solver (CPLEX), a genetic algorithm and a simulated annealing algorithm. Computational experiments demonstrate the superiority of the HDDE algorithm in terms of solution quality, robustness and run time.     

Order acceptance and scheduling policies for a make-to-order environment with family-dependent lead and batch setup times

In many make-to-order production situations with batch setup times, customer orders are grouped into family-dependent batches to limit the loss of capacity due to setups. These batches, however, cannot be too large, since the make-to-order character requires that orders have to be produced in time. This trade-off between setup time efficiency and due-date adherence creates a challenging scheduling problem referred to in the literature as the Customised Stochastic Lot Scheduling Problem. Typically, suppliers reduce the complexity of the production problem by quoting lead times that are equal for all customer families. This choice, however, is in many cases too restrictive. In this paper, we show quantitatively by means of Markov decision processes (MDPs) that using family-dependent lead times can result in a significant gain in profit as compared with using standard lead times. We develop a simple heuristic acceptance/scheduling policy, and demonstrate that this heuristic performs very well compared with the optimal policy of the MDP for a wide range of parameters.