Coordinated scheduling of customer orders with decentralized machine locations

We consider a scheduling model with two machines at different locations. Each job is composed of two tasks where each task must be processed by a specific machine. The finished tasks are shipped to a distribution center in batches before they are bundled together and delivered to customers. The objective is to minimize the sum of the delivery cost and customers' waiting costs. This model attempts to coordinate the production and delivery schedules on the decentralized machines while taking into consideration the shipping cost as well as the waiting time of the customers. We develop polynomial-time heuristic algorithms for this problem and analyze their worst-case performance. Computational experiments are conducted to test the effectiveness of the heuristics and to evaluate the benefits obtained by coordinating the production and delivery of the two decentralized machines.     

Optimization-based manufacturing scheduling with multiple resources, setup requirements, and transfer lots

The increasing demand for on-time delivery of products and low production cost is forcing manufacturers to seek effective schedules to coordinate machines and operators so as to reduce costs associated with labor, setup, inventory, and unhappy customers. This paper presents the modeling and resolution of a job shop scheduling system for J. M. Products Inc., whose manufacturing is characterized by the need to simultaneously consider machines and operators, machines requiring significant setup times, operators of different capabilities, and lots dividable into transfer lots. These characteristics are typical for many manufacturers, difficult to handle, and have not been adequately addressed in the literature. In our study, an integer optimization formulation with a separable structure is developed where both machines and operators are modeled as resources with finite capacities. Setups are explicitly considered following our previous work with additional penalties on excessive setups. By analyzing transfer lot dynamics, transfer lots are modeled by using linear inequalities. The objective is to maximize on-time delivery of products, reduce inventory, and reduce the number of setups. By relaxing resource capacity constraints and portions of precedence constraints, the problem is decomposed into smaller subproblems that are effectively solved by using a novel dynamic programming procedure. The multipliers are updated using the recently developed surrogate subgradient method. A heuristic is then used to obtain a feasible schedule based on subproblem solutions. Numerical testing shows that the method generates high quality schedules in a timely fashion.     

Finite capacity scheduling using a predetermined placement sequence

This paper presents a new heuristic for the finite capacity scheduling of factories. It treats the task of scheduling a factory the same as scheduling a large project that has many delivery points. The job placement sequence on machines is used as a link between infinite capacity schedules and finite capacity schedules. An ideal placement sequence is proposed from the infinite capacity backward schedule and this is embedded into the project network for finite capacity scheduling. This allows a finite capacity algorithm whose boundary condition is the most tightly packed schedule possible, and is also ideal from a cash flow perspective. The paper proposes a preference list of machines as an integral part of the scheduling process and shows how to switch between machines using preferences. It also shows how to integrate infinite and finite capacity schedules within the same algorithm by using a parameter called the constraint horizon. The heuristic is explained using input-output matrices and by working through an example of a project network. The example includes a discussion of circuits and a detailed explanation of how to implement the heuristic in a computer program.     

A knowledge acquisition model for selecting coordinate measuring machines using inductive learning

The objective of this study is to use the knowledge acquisition model of inductive learning to establish a selection system for coordinate measuring machines. In this paper, an example knowledge base for the selection of a coordinate measuring machine was induced and analyzed from the diffusive information in the example. The goal is to reduce the amount of knowledge related to the event so as to represent the knowledge in the knowledge base with the fewest number of rules possible. Then the concise decision tree is established by means of the knowledge acquisition model to describe the entire selection problem of coordinate measuring machines.     

Parallel-machine rescheduling with machine disruptions

In this study we consider a rescheduling problem on identical parallel machines. The rescheduling is undertaken because of a period of unavailability on one of the machines. We consider the total flow time as an efficiency measure and stability is gauged in terms of the number of jobs processed on different machines in the original and new schedules. We show that all efficient schedules with respect to efficiency and stability measures can be generated in polynomial time.     

Rolling-horizon lot-sizing when set-up times are sequence-dependent

The challenging problem of efficient lot sizing on parallel machines with sequence-dependent set-up times is modelled using a new mixed integer programming (MIP) formulation that permits multiple set-ups per planning period. The resulting model is generally too large to solve optimally and, given that it will be used on a rolling horizon basis with imperfect demand forecasts, approximate models that only generate exact schedules for the immediate periods are developed. Both static and rolling horizon snapshot tests are carried out. The approximate models are tested and found to be practical rolling horizon proxies for the exact model, reducing the dimensionality of the problem and allowing for faster solution by MIP and metaheuristic methods. However, for large problems the approximate models can also consume an impractical amount of computing time and so a rapid solution approach is presented to generate schedules by solving a succession of fast MIP models. Tests show that this approach is able to produce good solutions quickly.     

Shift scheduling for steppers in the semiconductor wafer fabrication process

In this paper, an approach is proposed for scheduling stepper machines that are acting as bottleneck machines in the semiconductor wafer fabrication process. We consider the problem of scheduling the steppers for an 8 hour shift, determining which types of wafer lots to work on each machine. The scheduling objective is to find the optimal stepper allocations such that the schedule meets target production quantities that have been derived from the given target Work-In-Process (WIP) levels. A Mixed Integer Programming (MIP) model is formulated, and three heuristic approaches are proposed and tested to approximately solve the M1P model. Numerical tests show that one of the proposed heuristics using linear programming relaxation of MIP generates, on average, schedules within 5° of the optimum values.     

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.     

A flowshop scheduling problem with two operations per job

This paper considers a special case of the flowshop scheduling problem where each job requires only two operations on specified machines and shows that this problem is NP-hard in the strong sense even if the first operation of all jobs is processed on the same machine and the number of machines performing the second operation equals two. For the case when the first operation of all jobs is performed on the same machine, it is sufficient to consider only permutation schedules for minimizing any regular measure of performance. Five polynomially bounded heuristic algorithms are described for minimizing makespan for this case and their performance in finding a minimum makespan schedule is theoretically and empirically evaluated.     

Minimising interference for scheduling two parallel machines with a single server

In this paper, we consider the problem of scheduling a set of jobs on two parallel machines with set-up times. The set-up has to be performed by a single server. The objective is to minimise the forced idle time. The problem of minimising the forced idle time (interference problem) is known to be unary NP-hard for the case of two machines and equal set-up and arbitrary processing times. We propose a mixed integer linear programming model, which describes a special class of schedules where the jobs from a list are scheduled alternatively on the machines, and a heuristic algorithm is tested on instances with up to 100,000 jobs. The computational results indicate that the algorithm has an excellent performance even for very large instances, where mostly an optimal solution is obtained within a very small computational time.     

Heuristics for minimizing total weighted tardiness in complex job shops

Semi-conductor manufacturing is arguably one of the most complex manufacturing processes in existence today. A semi-conductor wafer fabrication facility is comprised of batching machines, parallel machines, machines with sequence-dependent set-ups, and re-circulating product flow. The individual job release times and due dates combine with the other processing environment characteristics to form a ‘complex’ job shop scheduling problem. We first present a mixed-integer program (MIP) to minimize total weighted tardiness in a complex job shop. Since the problem is NP-hard, we compare a heuristic based on the MIP (MIP heuristic) with both a tuned version of a modified shifting bottleneck heuristic (SB heuristic) and three dispatching rules using random problem instances of a representative model from the literature. While the MIP heuristic typically produces superior schedules for problem instances with a small number of jobs, the SB heuristic consistently outperforms the MIP heuristic for larger problem instances. The SB heuristic's superior performance as compared to additional dispatching rules is also demonstrated for a larger, ‘real world’ dataset from the literature.     

数字化多轴向三维编织原理样机及其工艺研究

三维编织预制体是高性能复合材料增强相。三维编织装备的数字化程度决定了三维编织预制体的可设计性、成型精度和可追溯性。为解决传统编织机数字化程度低的瓶颈,本文研制了一种数字化多轴向水平放纱三维编织原理样机。根据步进驱动原理设计实现原理样机的六齿型空心轴拨盘,并通过建立纱线空间运动模型设计制备恒张力水平放置携纱器。采用Visual Studio设计开发基于Windows 7以上64位操作系统的CAE实时控制程序,以STM32微控制器为基础,设计原理样机的下位机硬件控制电路。根据空间运动学原理,在笛卡尔坐标系下建立纱线运动轨迹模型,模拟纱线的运动轨迹,并使用850D聚丙烯纤维进行验证实验。 运用本文设计的编织原理样机进行实验,获得的编织结构与仿真结果吻合的较好 ,证明了原理样机编织多层织物结构的可行性,同时验证了仿真结果的准确性。     

数控加工中心的位置误差补偿模型

本文以三轴数控加工中心为例,利用齐次矩阵建立了完备的数控加工中心的位置误差补偿模型,利用本文方法可以对三轴以上的多轴数控加工中心的位置误差进行建模,本文的建模方法和结论可以应用到三坐标测量机、工业机器人的位置误差模型的建立和位置误差补偿中去,以便在不增加制造成本的情况下,提高加工精度或测量精度,实现“不使用精密设备的精密加工”。     

Maintenance scheduling for a manufacturing system of machines with adjustable throughput

This paper considers the problem of analyzing and optimizing joint schedules of maintenance and throughput adjustment operations in manufacturing systems. The purpose of joint scheduling of maintenance and throughput changing operations is to maximize the cost benefits of maintenance operations in manufacturing systems in which some or all of the machines can execute their function under different process settings, resulting in different machine and system throughputs. Such a capability enables one to strategically slow down more degraded machines or accelerate freshly maintained machines so that production targets can be met and maintenance operations can be offset to times when they are less intrusive on the manufacturing process. A Monte-Carlo-simulation-based method is proposed for the evaluation of cost effectiveness of any schedule of maintenance and throughput changing operations, and a genetic-algorithm-based method is proposed to enable searching for schedules that would maximize the cost benefits of these operations. A matrix chromosome representation of the joint schedules of maintenance and throughput adjustment operations is introduced and several mechanisms of chromosome evolution and selection are proposed and analyzed in numerical simulations of such manufacturing systems. Results indicate a good ability for the newly proposed methods to achieve a tradeoff between cost benefits of production and losses due to maintenance operations through strategic allocation of maintenance and throughput changing actions.     

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 new method for workshop real time scheduling

Workshop real time scheduling is one of the key factors in improving manufacturing system efficiency. This is especially true for workshops in which various products are processed simultaneously, and use multipurpose machines. Real time scheduling is appropriate to handle perturbations in the environment of the manufacturing process, a major issue at the shop floor level. The products to be processed have release times and due dates and the resources are multipurpose machines. A decision support system for real time scheduling is described. It is based on an original approach, aiming at searching for characteristics of a set of schedules compatible with the main manufacturing constraints to be satisfied. This set of schedules is obtained by defining sequences of groups of permutable operations for every resource. A method to find such a set is described. We emphasize the use of this group sequence as a decision support system. Significant states and events requiring real time decisions are identified and three main types of decisions are analysed. For each of them, the proposed decision support system is detailed and explained.     

Minimising schedule cost via simulation optimisation: an application in pipe manufacturing

We present a method to minimise the cost of batch schedules for a pipe manufacturing facility. The method determines the sequence of production and start date of the batch considering raw material and finished goods holding cost, late delivery cost, and changeover. Our approach is designed to interface to the company's manufacturing execution system, and uses a simplified model of the production line for speed of execution. We demonstrate that methodology results in significant cost savings when compared to existing schedules.     

Hydrogel machines

As polymer networks infiltrated with water, hydrogels constitute the major components of the human body; and hydrogels have been widely used in applications that closely interact with biological organisms, such as tissue engineering, drug delivery, and biological research. More recently, owing to their superior softness, wetness, responsiveness, biocompatibility, and bioactivity, hydrogels are being intensively investigated for versatile functions in devices and machines including sensors, actuators, coatings, optics, electronics, and water harvesters. A nascent field named hydrogel machines rapidly evolves, exploiting hydrogels as key components for devices and machines. While there are reviews on individual categories of hydrogel machines in literature, a comprehensive discussion on various categories of hydrogel machines that systematically correlate hydrogels’ properties and machines’ functions is still missing in the field. This review is aimed to provide such a panoramic overview. We first classify various hydrogel machines into a number of categories according to their applications. For each category, we discuss (i) the working principles of the hydrogel machines, (ii) the specific properties of hydrogels that enable the key functions of the machines, and (iii) challenges faced by hydrogel machines and recent developments to address them. The field of hydrogel machines will not only translate fundamental understanding of hydrogels into new applications, but also shift the paradigm in machine design by integrating hydrogels that can potentially minimize physical and physiological mismatches with biological organisms.     

Modelling and integration of customer flexibility in the order commitment process for high mix low volume production

With increasing product variety and dynamic demand fluctuation, manufacturing industry is moving towards a high product mix and low order volume production environment. Consequently, the order commitment process is becoming one of the most important processes for manufacturing firms to meet individual customer's needs with limited resources. However, demands for shortened delivery lead time, diverse customer requirements and more frequent customer orders have made the order commitment task more challenging. This paper attempts to tackle these new challenges by incorporating not only manufacturing flexibility but also flexibility from the demand side. Customer flexibility is characterised by customer indifference to certain product attributes and/or delivery schedules. Intuitively, with the consideration of customer flexibility, both manufacturers’ and customers’ interests can be better served since the solution space of matching demand and supply can be extended beyond the traditional domain purely from a manufacturing perspective. To this end, a systematic approach is developed to characterise and model customer flexibility. A mixed-integer-programming model is formulated to provide optimal order commitment decisions.     

Two-machine shop scheduling with an uncapacitated interstage transporter

In this paper we study the two-machine flow shop and open shop problems to minimize the makespan with a single interstage transporter that may carry any number of jobs between the machines at a time. For each of these problems we present a best possible approximation algorithm within a class of schedules with at most two shipments. As a by-product of this research, for the problem of minimizing the makespan on parallel identical machines we analyze the ratio of the makespan for a non-preemptive schedule over the makespan of a preemptive schedule.