Computationally efficient neuro-dynamic programming approximation method for the capacitated re-entrant line scheduling problem

This paper presents a computationally efficient neuro-dynamic programming approximation method for the capacitated re-entrant line scheduling problem by reducing the number of feature functions. The method is based on a statistical assessment of the significance of the various feature functions. This assessment can be made by combining the weighted principal components with a thresholding algorithm. The efficacy of the new feature functions selected is tested by numerical experiments. The results indicate that the feature selection method presented here can extract a small number of significant features with the potential capability of providing a compact representation of the target value function in a neuro-dynamic programming framework. Moreover, the linear parametric architecture considered holds considerable promise as a way to provide effective and computationally efficient approximations for an optimal scheduling policy that consistently outperforms the heuristics typically employed.     

Multi-criteria optimisation-based dynamic scheduling for controlling FMS

This study deals with controlling flexible manufacturing systems (FMS) operating in volatile production environments. Most studies that address this issue use some sort of adaptive scheduling that enables the FMS to cope with the randomness and variability efficiently. The methods presented in the literature are usually based on heuristics and use simple dispatching rules. They do not consider changing the decision criteria dynamically as the system conditions change. In contrast to previous studies, the present study focuses on developing a control mechanism for dynamic scheduling that is based on incremental optimisation. This means that each time a scheduling decision is made, the local optimisation problem is solved such that the next jobs to be processed on machines are selected. The objective function (dominant decision criterion) for this optimisation problem is selected dynamically based on production order requirements, actual shop-floor status and system priorities. The proposed multi-criteria optimisation-based dynamic scheduling methodology was evaluated and compared with some known scheduling rules/policies. The results obtained demonstrate the superiority of the suggested methodology as well as its capability to cope with a multi-criteria environment.     

Master production scheduling: a multiple-objective linear programming approach

This paper describes and discusses a mathematical model for developing a Master Production Schedule. The model considers multiple objectives and several typical constraints. The input parameters to the model are determined and an example is solved to illustrate the procedure.     

Energetic reasoning and mixed-integer linear programming for scheduling with a continuous resource and linear efficiency functions

This paper addresses a scheduling problem with a continuously divisible, cumulative and renewable resource with limited capacity. During its processing, each task consumes a part of this resource, which lies between a minimum and a maximum requirement. A task is finished when a certain amount of energy is received by it within its time window. This energy is received via the resource and an amount of resource is converted into an amount of energy with a non-decreasing and continuous function. The goal is to find a feasible schedule, which is already NP-complete, and then to minimize the resource consumption. For the case where all functions are linear, we present two new mixed-integer linear programs (MILP), as well as improvements of an existing formulation. We also present a detailed version of the adaptation of the well-known “left-shift/right-shift” satisfiability test for the cumulative constraint and the associated time-window adjustments to our problem. For this test, three ways of computing relevant intervals are described. Finally, a hybrid branch-and-bound using both the satisfiability test and the MILP is presented with a new heuristic for choosing the variable on which the branching is done. Computational experiments on randomly generated instances are reported in order to compare all of these solution methods.     

Mixed-integer linear programming method for multi-degree and multi-hoist cyclic scheduling with time windows

Multi-degree cyclic hoist scheduling and multi-hoist cyclic scheduling are both capable of improving the throughput in an automatic electroplating line. However, previous research on integrated multi-degree and multi-hoist cyclic scheduling is rather limited. This article develops an optimal mixed-integer linear programming model for the integrated multi-degree and multi-hoist cyclic scheduling with time window constraints. This model permits overlap on hoist coverage ranges, and it proposes new formulations to avoid hoist collisions, by which time window constraints and tank capacity constraints are also formulated. A set of available benchmark instances and newly generated instances are solved using the CPLEX solver to test the performance of the proposed method. Computational results demonstrate that the proposed method outperforms the zone partition heuristic without overlapping, and the throughputs are improved by a significant margin using the proposed method, especially for large-size instances.     

Lyapunov function construction for ordinary differential equations with linear programming

An algorithm that derives a linear program for an ordinary differential equation is presented, of which a feasible solution defines a continuous piecewise affine linear Lyapunov function for the differential equation. The linear program can be generated for an arbitrary region containing an equilibrium of the differential equation. The domain of the Lyapunov function is the region used in the generation of the linear program. The Lyapunov function secures the asymptotic stability of the equilibrium and gives a lower bound on its region of attraction.     

Fuzzy inference-based multiple criteria FMS scheduling

This paper proposes a fuzzy inference-based scheduling decision for flexible manufacturing systems (FMS) with multiple objectives. The objectives have different and dynamic preference levels. It is inferred that the changes in the production environment may be sensed by environmental variables. The detected changes are input in a fuzzy inference mechanism, which outputs the current preference levels of all objectives. A multiple criteria scheduling decision is then made, using the partitioned combination of the preference levels. An example of application is presented. Simulation results show very good performance for the proposed system.     

Automatic design of scheduling policies for dynamic flexible job shop scheduling via surrogate-assisted cooperative co-evolution genetic programming

At present, a lot of references use discrete event simulation to evaluate the fitness of evolved rules, but which simulation configuration can achieve better evolutionary rules in a limited time has not been fully studied. This study proposes three types of hyper-heuristic methods for coevolution of the machine assignment rules (MAR) and job sequencing rules (JSR) to solve the DFJSP, including the cooperative coevolution genetic programming with two sub-populations (CCGP), the genetic programming with two sub-trees (TTGP) and the genetic expression programming with two sub-chromosomes (GEP). After careful parameter tuning, a surrogate simulation model is used to evaluate the fitness of evolved scheduling policies (SP). Computational simulations and comparisons demonstrate that the proposed surrogate-assisted CCGP method (CCGP-SM) shows competitive performance with other evolutionary approaches using the same computation time. Furthermore, the learning process of the proposed methods demonstrates that the surrogate-assisted GP methods help accelerating the evolutionary process and improving the quality of the evolved SPs without a signi?cant increase in the length of SP. In addition, the evolved SPs generated by the CCGP-SM show superior performance as compared with existing rules in the literature. These results demonstrate the effectiveness and robustness of the proposed method.     

A comparison of mixed-integer linear programming models for workforce scheduling with position-dependent processing times

Only a few studies in the available scientific literature address the problem of having a group of workers that do not share identical levels of productivity during the planning horizon. This study considers a workforce scheduling problem in which the actual processing time is a function of the scheduling sequence to represent the decline in workers’ performance, evaluating two classical performance measures separately: makespan and maximum tardiness. Several mathematical models are compared with each other to highlight the advantages of each approach. The mathematical models are tested with randomly generated instances available from a public e-library.     

A mixed integer linear programming solution for single hoist multi-degree cyclic scheduling with reentrance

This article considers single hoist multi-degree cyclic scheduling problems with reentrance. Time window constraints are also considered. Firstly, a mixed integer programming model is formulated for multi-degree cyclic hoist scheduling without reentrance, referred to as basic lines in this article. Two valid inequalities corresponding to this problem are also presented. Based on the model for basic lines, an extended mixed integer programming model is proposed for more complicated scheduling problems with reentrance. Phillips and Unger's benchmark instance and randomly generated instances are applied to test the model without reentrance, solved using the commercial software CPLEX. The efficiency of the model is analysed based on computational time. Moreover, an example is given to demonstrate the effectiveness of the model with reentrance.     

Improved mixed-integer linear programming model and heuristics for bi-objective single-machine batch scheduling with energy cost consideration

This article addresses bi-objective single-machine batch scheduling under time-of-use electricity prices to minimize the total energy cost and the makespan. The lower and upper bounds on the number of formed batches are first derived and a continuous-time mixed-integer linear programming model is proposed, which improves an existing discrete-time model in the literature. Two improved heuristics are proposed based on the improved model. Computational experiments demonstrate that the improved model and heuristics can run hundreds of times faster than the existing ones for large-size instances.     

FMS中CAPP与CAM集成技术的研究

介绍了一个适用于FMS的CAPP／CAM集成系统。它由创成法CAPP系统，NC自动编程系统和它们之间的接口等主要部分组成。系统采用基于特征的零件描述方法作为集成环境下统一的零件信息模型。由CAPP系统生成的工艺规程，通过接口文件自动传输给NC编程系统，经过特征识别后，从特征NC程序库中调用相应的特征数控程序，实现NC自动编程，为检验NC程序的错误，系统还具有刀具轨迹仿真功能，系统用户界面友好，经加工验证，可用于生产。     

Integration of inductive learning and neural networks for multi-objective FMS scheduling

In this paper, we propose an integrated approach of inductive learning and competitive neural networks for developing multi-objective flexible manufacturing system (FMS) schedulers. Simulation and competitive neural networks are applied sequentially to extract a set of classified training data which is used to create a compact set of scheduling rules through inductive learning. The FMS scheduler can assist the operator to make decisions in real time, while satisfying multiple objectives desired by the operator. A simulation-based experiment is performed to evaluate the performance of the resulting scheduler.     

Identifying differentially expressed pathways via a mixed integer linear programming model

The identification of genes and pathways involved in biological processes is a central problem in systems biology. Recent microarray technologies and other high-throughput experiments provide information which sheds light on this problem. In this article, the authors propose a new computational method to detect active pathways, or identify differentially expressed pathways via integration of gene expression and interactomic data in a sophisticated and efficient manner. Specifically, by using signal-to-noise ratio to measure the differentially expressed level of networks, this problem is formulated as a mixed integer linear programming problem (MILP). The results on yeast and human data demonstrate that the proposed method is more accurate and robust than existing approaches.     

A mixed-integer linear programming model for integrated production and preventive maintenance scheduling in the capital goods industry

The scheduling literature is extensive, but much of this work is theoretical and does not capture the complexity of real world systems. Capital goods companies produce products with deep and complex product structures, each of which requires the coordination of jobbing, batch, flow and assembly processes. Many components require numerous operations on multiple machines. Integrated scheduling problems simultaneously consider two or more simultaneous decisions. Previous production scheduling research in the capital goods industry has neglected maintenance scheduling and used metaheuristics with stochastic search that cannot guarantee an optimal solution. This paper presents a novel mixed integer linear programming model for simultaneously solving the integrated production and preventive maintenance scheduling problem in the capital goods industry, which was tested using data from a collaborating company. The objective was to minimise total costs including: tardiness and earliness penalty costs; component and assembly holding costs; preventive maintenance costs; and set-up, production, transfer and production idle time costs. Thus, the objective function and problem formulation were more extensive than previous research. The tool was successfully tested using data obtained from a collaborating company. It was found that the company’s total cost could be reduced by up to 63.5%.     

A competitive neural network approach to multi-objective FMS scheduling

The main contribution of this paper is the development of a multi-objective FMS scheduler which is designed to maximally satisfy the desired values of multiple objectives set by the operator. For each production interval, a decision rule for each decision variable is chosen by the FMS scheduler. A competitive neural network is applied to present fast but good decision rules to the operator. A unique feature of the FMS scheduler is that the competitive neural network generates the next decision rules based on the current decision rules, system status and performance measures. A commercial FMS is simulated to prove the effectiveness of the FMS scheduler. The result shows that the FMS scheduler can successfully satisfy multiple objectives.     

A fuzzy logic modelling of dynamic scheduling in FMS

This paper is concerned with scheduling in flexible manufacturing systems (FMSs) using a fuzzy logic (FL) approach. Four fuzzy input variables: machine allocated processing time, machine priority, due date priority and setup time priority are defined. The job priority is the output fuzzy variable, showing the priority status of a job to be selected for next operation on a machine. The model will first select the machines and then assign operations based on a multi-criteria scheduling scheme. The performance of the approach is compared against established methods reported in the literature. The performance measures considered average machine utilisation, meeting due dates, setup times, work in process and mean flow times. The test results demonstrate the superiority of the fuzzy logic approach in most performance measures.     

Concave programming and piece-wise linear programming

This paper discusses the mathematical foundations of a technique that has been used extensively in structural optimization.^1–6 Two basic problems are considered. The first of these is the concave programming problem which consists of finding the global minimum of ‘piece-wise concave functions’ on ‘piece-wise concave sets’. Since any function can be approximated by a piece-wise concave function, this method could in principle be used to find the global minimum in non-convex optimization problems. The second one is the piece-wise linear programming problem in which the objective function is convex and piece-wise linear. The iterative method outlined for handling this problem is shown to be much more efficient than the standard simplex method of linear programming.     

Simple method for minimax linear approximation of the transfer function of a measurement device

Translated from Izmeritel'naya Tekhnika, No. 3, pp. 19–21, March, 1992.     

Dynamic scheduling of FMS using a real-time genetic algorithm

The paper presents a genetic algorithm capable of generating optimised production plans in flexible manufacturing systems. The ability of the system to generate alternative plans following part-flow changes and unforeseen situations is particularly stressed (dynamic scheduling). Two contrasting objectives represented by the reduction of machine idle-times, thanks to dynamic scheduling computation and the reduction of the makespan, are taken into account by the proposed system. The key-point is the real-time response obtained by an optimised evolutionary strategy capable of minimising the number of genetic operations needed to reach the optimal schedule in complex manufacturing systems.