一类新型批处理机调度问题的理论分析

钢卷在冷轧生产中,为了改进其性能,需要在罩式炉进行退火,退火过程由加热、保温和降温三段组成,而这三段处理时间由于工艺上的要求不能归结为一个时间,这与传统批处理机调度有明显的差别.对新型批处理机的总加权完成时间最小化问题建立了非线性整数规划模型,开发了基于动态规划的启发式算法.通过理论分析,获得该算法的误差性能比为3.对于三段中的某一段板卷的处理时间相同的情况,证明了启发式算法的误差性能比是2,而且证明是紧界.对于三段中的某二段板卷的处理时间相同的情况,证明了启发式算法是最优算法.对启发式算法扩展到带有任意段的加工时间的一般情况进行了性能分析.     

MULTI-MACHINE,MULTI-PRODUCT PRODUCTION SCHEDULING AND INVENTORY CONTROL

This paper deals with a multi-machine, multi-product lot size determination and scheduling problem. The model developed here considers not only the usual inventory-related operational cost, but also the costs that depend on under- or over-utilization of available men and machines. It penalizes overtime or idle time at any facility. The solution minimizes the inventory and resource-related costs and not just inventory costs. A heuristic is developed to determine the solution from the model and to modify it, as necessary, to obtain a conflict-free, repetitive, and cyclic production schedule for an infinite horizon. Although this model is developed for a manufacturing situation, the words machine, job, and machine shop are used in a symbolic sense, and hence the model can be used in practice in a variety of circumstances.     

Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach

In today's fast-paced Just-In-Time and mass customization manufacturing in a sequence-dependent setup environment, the challenge of making production schedules to meet due-date requirements is becoming a more complex problem. Unfortunately, much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of minimizing tardiness, a common measure of due-date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performance was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can rework schedules frequently to react to variations in the schedule. The algorithm is invaluable for ‘on-line’ production scheduling and ‘last-minute’ changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environments, such as multiple machines with a higher number of jobs in the sequence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in solving complex scheduling problems.     

The Ordered Cutting Stock Problem

The one‐dimensional cutting stock problem (CSP) is a classic combinatorial optimization problem in which a number of parts of various lengths must be cut from an inventory of standard‐size material. The classic CSP ensures that the total demand for a given part size is met but ignores the fact that parts produced by a given cutting pattern may be destined for different jobs. As a result, applying the classic CSP in a dynamic production environment may result in many jobs being open (or partially complete) at any point in time—requiring significant material handling or sorting operations. This paper identifies and discusses a new type of one‐dimensional CSP, called the ordered CSP, which explicitly restricts to one the number of jobs in a production process that can be open, or in process, at any given point in time. Given the growing emphasis on mass customization in the manufacturing industry, this restriction can help lead to a reduction in both in‐process inventory levels and material handling activities. A formal mathematical formulation is provided for the new CSP model, and its applicability is discussed with respect to a production problem in the custom door and window manufacturing industry. A genetic algorithm (GA) solution approach is then presented, which incorporates a customized heuristic for reducing scrap levels. Several different production scenarios are considered, and computational results are provided that illustrate the ability of the GA‐based approach to significantly decrease the amount of scrap generated in the production process.     

Approximations to Optimal k‐Unit Cycles for Single‐Gripper and Dual‐Gripper Robotic Cells

We consider the problem of scheduling operations in bufferless robotic cells that produce identical parts using either single‐gripper or dual‐gripper robots. The objective is to find a cyclic sequence of robot moves that minimizes the long‐run average time to produce a part or, equivalently, maximizes the throughput. Obtaining an efficient algorithm for an optimum k‐unit cyclic solution (k ≥ 1) has been a longstanding open problem. For both single‐gripper and dual‐gripper cells, the approximation algorithms in this paper provide the best‐known performance guarantees (obtainable in polynomial time) for an optimal cyclic solution. We provide two algorithms that have a running time linear in the number of machines: for single‐gripper cells (respectively, dual‐gripper cells), the performance guarantee is 9/7 (respectively, 3/2). The domain considered is free‐pickup cells with constant intermachine travel time. Our structural analysis is an important step toward resolving the complexity status of finding an optimal cyclic solution in either a single‐gripper or a dual‐gripper cell. We also identify optimal cyclic solutions for a variety of special cases. Our analysis provides production managers valuable insights into the schedules that maximize productivity for both single‐gripper and dual‐gripper cells for any combination of processing requirements and physical parameters.     

加工能力受限的单机干扰管理研究

针对单机环境下最小化加权折扣加工时间和的排序问题,研究如何应对可预见的干扰事件。由于干扰事件使得机器加工能力受限,初始最优加工时间表不再可行,采用外包的方式来进行干扰管理。构建了排序模型,同时考虑原目标和与初始计划偏离的扰动目标,选择外包工件集并对所有工件进行重排序。为了求解得到的双目标排序问题,基于理想点法设计了一种动态规划算法和量子遗传算法相结合的算法。最后通过一个数值算例说明,该排序模型对于求解加工能力受限的单机干扰管理问题是有效的。     

MANAGING CYCLIC INVENTORIES

Cyclic inventory is the buffer following a machine that cycles over a set of products, each of which is subsequently consumed in a continuous manner. Scheduling such a machine is interesting when the changeover times from one product to another are non‐trivial—which is generally the case. This problem has a substantial literature, but the common practices of “lot‐splitting” and “maximization of utilization” suggest that many practitioners still do not fully understand the principles of cyclic inventory. This paper is a tutorial that demonstrates those principles. We show that cyclic inventory is directly proportional to cycle length, which in turn is directly proportional to total changeover time, and inversely proportional to machine utilization. We demonstrate the virtue of “maximum changeover policies” in minimizing cyclic inventory—and the difficulty in making the transition to an increased level of demand. In so doing, we explicate the different roles of cyclic inventory, transitional inventory, and safety stock. We demonstrate the interdependence of the products in the cycle—the lot‐size for one product cannot be set independently of the remaining products. We also give necessary conditions for consideration of improper schedules (i.e., where a product can appear more than once in the cycle), and demonstrate that both lot‐splitting and maximization of utilization are devastatingly counter‐productive when changeover time is non‐trivial.     

Heterogeneous dispatching rules in job and flow shops

This paper reports the results of a study of the use of heterogeneous dispatching rules for the scheduling of work in a job shop. The methodology employed included discrete event simulation, using rule combinations determined by prior genetic algorithm searches and generalization using neural networks. Eight dispatching rules were considered, including first in first out (FIFO), earliest due date ( EDD), shortest processing time (SPT), slack/ number of operations (SLK), critical ratio (CR), modified due date (MDD), modified operation due date (MOD), and apparent tardiness cost (ATC). A three-machine job shop was studied, in which three work organizations were employed, pure flow (fixed sequence), pure job shop ( random sequence), and a hybrid shop where flow is random but with unequal probabilities. Three levels of machine loading were used and average tardiness was used as the performance measure. In most cases, modified due date and apparent tardiness cost were the best rules. The application of the best rules effected the results primarily when applied to bottleneck machines or the first machine in a pure flow shop. Nearly any other rule was acceptable on non-botdeneck machines except FIFO and CR, which consistently perform poorly. No major advantage of mixing rules was found.     

Online algorithms for maximizing weighted throughput of unit jobs with temperature constraints

We consider a temperature-aware online deadline scheduling model. The objective is to schedule a number of unit jobs, with release dates, deadlines, weights and heat contributions, to maximize the weighted throughput subject to a temperature threshold. We first give an optimally competitive randomized algorithm. Then we give a constant competitive randomized algorithm that allows a tradeoff between the maximum heat contribution of jobs and the competitiveness. Finally we consider the multiple processor case and give several tight upper and lower bounds.     

Single machine group scheduling to minimize mean flow time subject to due date constraints

This paper considers a single machine group scheduling problem. All jobs are classified into groups and the jobs within a group are processed contiguously on the machine. A sequence-independent setup time is incurred between each two consecutively scheduled groups. This paper presents a solution procedure which utilizes Smith's algorithm and a proposed modified Smith's algorithm to find an optimal job sequence and an optimal group sequence which minimizes the mean flow time of jobs subject to the constraint that no jobs are tardy. The complexity of the algorithm is shown to have a polynomial running time in the number of groups and jobs.     

The no-wait job shop with regular objective: a method based on optimal job insertion

The no-wait job shop problem (NWJS-R) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is prescribed. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The problem consists in finding a schedule that minimizes a general regular objective function. We study the so-called optimal job insertion problem in the NWJS-R and prove that this problem is solvable in polynomial time by a very efficient algorithm, generalizing a result we obtained in the case of a makespan objective. We then propose a large neighborhood local search method for the NWJS-R based on the optimal job insertion algorithm and present extensive numerical results that compare favorably with current benchmarks when available.     

加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。     

Joint pricing and ordering policy for a deteriorating inventory with partial backlogging

In this paper, a deterministic inventory model for deteriorating items with time-dependent backlogging rate is developed. The demand and deterioration rate are known, continuous, and differentiable function of price and time, respectively. Under these general assumptions, we first prove that the optimal replenishment schedule not only exists but is unique, for any given selling price. Next, we show that the total profit is a concave function of price when the replenishment schedule is given. We then provide a simple algorithm to find the optimal selling price and replenishment schedule for the proposed model. Finally, we use a numerical example to illustrate the algorithm.     

Processing in a multi-machine batch manufacturing system with sequence dependent cost

Many workcells in batch manufacturing systems are populated with multiple, nonidentical machines that perform similar tasks. Because of the size of a batch when a job arrives, it may be uneconomical to set up two or more machines to process the same job simultaneously. An economic decision has to be made as regards which machine in the cell to assign the job. Likewise, many multi-operation jobs can be processed using one of several feasible operation sequences that may lead to different total manufacturing costs. The cost differences are the result of several factors, among which are processing time and cost dependencies between operations, fixturing requirements, and material handling requirements. When the workcell machine selection decision is considered along with the operation sequencing decision, determination of the best machine in a cell and the best operation sequence for the batch is a non-trivial task. In this paper, we address the problem of selecting the best machine within a cell and the best operation sequence for a batch when operation cost is machine and sequence dependent. The problem is modeled mathematically and solved using a heuristic algorithm. The performance of the algorithm is compared with that of an exact solution procedure.     

具有优先约束和加工时间依赖开工时间的单机排序问题

研究工件间的优先约束为串并有向图的单机加权总完工时间问题,通过证明在工件加工时间是开工时间的线性函数的情况下,模块M的ρ因子最大初始集合I中的工件优先于模块M中的其它工件加工,并且被连续加工所得的排序为最优排序,从而将Lawler用来求解约束为串并有向图的单机加权总完工时间问题的方法推广到这个问题上来。     

Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling

We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker ( 2014 ) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.     

Improving throughput for an electronic assembly line using a constraint analysis methodology

Electronic assembly operations are vital to industries such as telecommunications, computers and consumer electronics. This paper presents a constraint analysis methodology for planning and improving electronic assembly operations that draws on concepts from queueing theory, simulation and production planning. The proposed methodology identifies the operational bottleneck and predicts the utilization, throughput and lead time of the assembly line. It also quantifies the relationship between yields and utilization for the assembly operations. A case study is presented that applies the methodology at an Ericsson, Inc., telecommunications equipment assembly facility. The constraint analysis methodology provided valuable decision support as the managers of Ericsson evaluated the costs and benefits of additional production capacity. Although the focus of this paper is electronic assembly operations, the methodology can be applied to general flow line assembly systems with feedback loops for test and rework under dedicated high-volume production.     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

Development of simulation-based production execution system in a shipyard: a case study for a panel block assembly shop

The management of a panel block shop in a shipyard is a complex process that entails the largest amount of work and in which many decisions are involved. Shipbuilders have considered the process as a bottleneck since every panel for every ship must be processed through the shop. The objective of this research is to carry out a materials flow analysis to maximise process productivity and to place simulation optimisation technology in the hands of decision makers, such as production planners and supervisors. In this article, a production execution planning system is proposed for panel block operations utilising discrete-event simulation and simulated annealing. The simulation model was validated using a real production scenario and the comparison showed a very favourable agreement between the actual panel shop and the simulation model. The proposed system supports production planners by general dispatching rules and optimisation to make better scheduling decisions on the shop floor. The system will provide a complete schedule that is at least as clear and accurate as any schedule currently obtained.     

Optimal semi-online algorithm for scheduling with rejection on two uniform machines

In this paper we consider a semi-online scheduling problem with rejection on two uniform machines with speed 1 and s≥1, respectively. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. Further, two rejection strategies are permitted thus an algorithm can propose two different schemes, from which the better solution is chosen. For the above version, we present an optimal semi-online algorithm H that achieves a competitive ratio ρ _H (s) as a piecewise function in terms of the speed ratio s.