Parallel-machine,multiple-product-type,continuous-time scheduling: decomposable cases

This paper considers a manufacturing system where multiple-product-types are produced on a set of parallel machines. The production quantity for each product-type in a planning horizon is predetermined. However, the planning horizon is not fixed, and a cost must be paid for each unit of time in the horizon. Inventory holding costs are incurred due to storing products in the buffer placed after each machine. In addition, a production cost is incurred if a machine is not idle. Our objective is to schedule the production so that inventory, production, and planning horizon costs are minimized. With the aid of the maximum principle, this continuous-time scheduling problem is studied, and the conditions such that the problem can be decomposed into a set of well-structured, discrete-time sub-problems are derived. Consequently, several solvable cases are identified, and their corresponding polynomial-time algorithms are suggested.     

Hierarchical production control for a flow shop with dynamic setup changes and random machine breakdowns

In this paper, we study a manufacturing system consisting of two machines separated by two intermediate buffers, and capable of producing two different products. Each product requires a constant processing time on each of the machines. Each machine requires a constant non-negligible setup change time from one product to the other. The demand rate for each product is considered to be piecewise constant. Each machine undergoes failure and repair. The time-to-failure and time-to-repair are exponentially distributed random variables. The setup change and processing operations are resumable. We model our system as a continuous time, continuous flow process. An optimal control problem is formulated for the system to minimize the total expected discounted cost over an infinite horizon. To determine the optimal control policy structure, a discrete version of the problem is solved numerically using a dynamic programming formulation with a piecewise linear penalty function. A real-time control algorithm is then developed with the objective of maintaining low work-in-process inventory and keeping the production close to the demand. The algorithm uses a hierarchical control structure to generate the loading times for each product on each machine in real time and to respond to random disruptions in the system. The system is simulated using this algorithm to study its performance. The performance of the algorithm is also compared to alternative policies.     

A Service Level Agreement Aware Online Algorithm for Virtual Machine Migration

The demand for cloud computing has increased manifold in the recent past. More specifically, on-demand computing has seen a rapid rise as organizations rely mostly on cloud service providers for their day-to-day computing needs. The cloud service provider fulfills different user requirements using virtualization - where a single physical machine can host multiple Virtual Machines. Each virtual machine potentially represents a different user environment such as operating system, programming environment, and applications. However, these cloud services use a large amount of electrical energy and produce greenhouse gases. To reduce the electricity cost and greenhouse gases, energy efficient algorithms must be designed. One specific area where energy efficient algorithms are required is virtual machine consolidation. With virtual machine consolidation, the objective is to utilize the minimum possible number of hosts to accommodate the required virtual machines, keeping in mind the service level agreement requirements. This research work formulates the virtual machine migration as an online problem and develops optimal offline and online algorithms for the single host virtual machine migration problem under a service level agreement constraint for an over-utilized host. The online algorithm is analyzed using a competitive analysis approach. In addition, an experimental analysis of the proposed algorithm on real-world data is conducted to showcase the improved performance of the proposed algorithm against the benchmark algorithms. Our proposed online algorithm consumed 25% less energy and performed 43% fewer migrations than the benchmark algorithms.     

Job shop scheduling with alternative machines

In this paper we investigate the problem of minimizing the mean flow time in a general job shop type machining system with alternative machine tool routeings. An analytical formulation of the problem as a mixed integer programming is developed. An efficient algorithm based on this formulation is developed to solve the problem by decomposing it into subproblems that are easier to solve. The algorithm solves large problems in relatively short time. A second algorithm based on the SPT rule is developed and its performance is compared with the first algorithm. A greedy procedure is also developed for the case when a penalty cost is associated with adding alternative machines. Numerical examples are given to demonstrate the use of the above algorithms.     

A mathematical formulation and anarchic society optimisation algorithms for integrated scheduling of processing and transportation operations in a flow-shop environment

This paper addresses a permutation flow-shop scheduling problem where there are a finite number of transporters to carry jobs from each machine to its subsequent machine. The problem is first formulated as a mixed-integer linear programme, and then two anarchic society optimisation (ASO) algorithms are developed to solve large-sized instances of the problem. The numerical experience shows that the ASO algorithms are considerably effective and efficient. Finally, a sensitivity analysis is carried out to study the performance of the manufacturing system versus the transportation times and the number of transporters.     

A rework-based dispatching algorithm for module process in TFT-LCD manufacture

This paper presents development of a scheduling methodology for module processing in thin film transistor liquid crystal display (TFT-LCD) manufacturing. The problem is a parallel machine scheduling problem with rework probabilities, sequence-dependent setup times and due dates. It is assumed that rework probability for each job on a machine can be given through historical data acquisition. The dispatching algorithm named GRPD (greedy rework probability with due-dates) is proposed in this paper focusing on the rework processes. The performance of GRPD is measured by the six diagnostic indicators. A large number of test problems are randomly generated to evaluate the performance of the proposed algorithm. Computational results show that the proposed algorithm is significantly superior to existing dispatching algorithms for the test problems.     

A variable neighbourhood search algorithm for the flexible job-shop scheduling problem

The flexible job-shop scheduling problem (FJSP) is a generalisation of the classical job-shop scheduling problem which allows an operation of each job to be executed by any machine out of a set of available machines. FJSP consists of two sub-problems which are assigning each operation to a machine out of a set of capable machines (routing sub-problem) and sequencing the assigned operations on the machines (sequencing sub-problem). This paper proposes a variable neighbourhood search (VNS) algorithm that solves the FJSP to minimise makespan. In the process of the presented algorithm, various neighbourhood structures related to assignment and sequencing problems are used for generating neighbouring solutions. To compare our algorithm with previous ones, an extensive computational study on 181 benchmark problems has been conducted. The results obtained from the presented algorithm are quite comparable to those obtained by the best-known algorithms for FJSP.     

A PSO-based approach to cell formation problems with alternative process routings

Group technology (GT) has been extensively applied to cellular manufacturing system (CMS) design for decades due to many benefits such as decreased number of part movements among cells and increased machine utilisation in cells. This paper considers cell formation problems with alternative process routings and proposes a discrete particle swarm optimisation (PSO) approach to minimise the number of exceptional parts outside machine cells. The approach contains two main steps: machine partition and part-routing assignment. Through inheritance and random search, the proposed algorithm can effectively partition machines into different cells with consideration of multiple part process routings. The computational results are compared with those obtained by using simulated annealing (SA)-based and tabu search (TS)-based algorithms. Experimental results demonstrate that the proposed algorithm can find equal or fewer exceptional elements than existing algorithms for most of the test problems selected from the literature. Moreover, the proposed algorithm is further tailed to incorporate various production factors in order to extend its applicability. Four sample cases are tested and the results suggest that the algorithm is capable of solving more practical cell formation problems.     

A GRASP algorithm for flexible job-shop scheduling problem with limited resource constraints

A greedy randomised adaptive search procedure (GRASP) is an iterative multi-start metaheuristic for difficult combinatorial optimisation. The GRASP iteration consists of two phases: a construction phase, in which a feasible solution is found and a local search phase, in which a local optimum in the neighbourhood of the constructed solution is sought. In this paper, a GRASP algorithm is presented to solve the flexible job-shop scheduling problem (FJSSP) with limited resource constraints. The main constraint of this scheduling problem is that each operation of a job must follow an appointed process order and each operation must be processed on an appointed machine. These constraints are used to balance between the resource limitation and machine flexibility. The model objectives are the minimisation of makespan, maximum workload and total workload. Representative benchmark problems are solved in order to test the effectiveness and efficiency of the GRASP algorithm. The computational result shows that the proposed algorithm produced better results than other authors’ algorithms.     

JOB ASSIGNMENT ALGORITHMS ON UNIFORM PARALLEL MACHINES

Uniform parallel machine scheduling problems with a makespan measure cannot generally be solved within polynomial time complexity. This paper considers special problems with a single type of job on the uniform parallel machines, where each machine is available at a given ready time. Also the machine can be restricted on the number of jobs to be processed. The objective is to develop job assignment or batching algorithms which minimize makespan. When all the machines are available at time zero and have no restriction on the number of assignable jobs, a lower bound and optimal solution properties are derived. Based upon these properties, a polynomial algorithm is suggested to find the optimal job assignment on each machine. Three generalized problems are considered under the following situations: (1) some machines have capacity restrictions on the production batch, (2) each machine has its ready time, and (3) the jobs require series-parallel operations. The generalized problems arc also characterized and polynomial algorithms are developed for the same aim of optimal job assignment, except for the case of series-parallel operations. A heuristic algorithm is suggested with numerical tests for the series-parallel operations problem     

Simulated annealing-based multiobjective algorithms and their application for system reliability

The paper presents five simulated annealing based multiobjective algorithms - SMOSA, UMOSA, PSA, PDMOSA and WMOSA. All of these algorithms aim to find a Pareto set of solutions of a system reliability multiobjective optimization problem in a short time. In each algorithm the solution vector explores its neighborhood in a way similar to that of Classical Simulated Annealing. All the algorithms are problem-specific and if the true Pareto-optimal set has few solutions, UMOSA, SMOSA, PSA and WMOSA work better than PDMOSA. In some cases, PSA works the best. The computational cost is least in the case of the WMOSA algorithm since it does not need to use the penalty function approach to handle the constraints, and is the maximum with PDMOSA since it requires two sets of Pareto solutions.     

A new approach for loop machine layout problem integrating proximity constraints

This paper focuses on the machine arrangement problem on common loop network in a flexible manufacturing system. Existing studies aim to place machines at pre-fixed positions around a loop network. This problem is considered as a permutation problem that aims to find the best combination to reduce generated costs. In this work, we try to add more complexity to this problem by respecting the proximity constraints, defined by the experts, between the machines. To do this, we propose an algorithm based on direct distance measure. Logically, proximity constraints are checked using direct distances but costs are calculated using travelled distances. Throughout this study, we seek the best machine layout in four transport system configuration types to minimise the sum of flow time distances. Comparing our algorithm results with two hybrid genetic algorithms, the empirical results show that the proposed algorithm provides the most suitable solutions.     

An adaptive scheduling algorithm for a parallel machine problem with rework processes

The development of a scheduling methodology for a parallel machine problem with rework processes is presented in this paper. The problem is to make a schedule for parallel machines with rework probabilities, due-dates, and sequence dependent setup times. Two heuristics are developed based on a dispatching algorithm and problem-space-based search method. In order to evaluate the efficacy of the proposed algorithms, six performance indicators are considered: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of tardy jobs, and the number of reworks. This paper shows how these algorithms can adaptively capture the characteristics of manufacturing facilities for enhancing the performance under changing production environments. Extensive experimental results show that the proposed algorithms give very efficient performance in terms of computational time and each objective value.     

A robust cell formation approach for varying product demands

In cellular manufacturing environments, manufacturing cells are generally formed based on deterministic product demands. In this paper, we consider a system configuration problem with product demands expressed in a number of probabilistic scenarios. An optimization model integrating cell formation and part allocation is developed to generate a robust system configuration to minimize machine cost and expected inter-cell material handling cost. A two-stage Tabu search based heuristic algorithm is developed to find the optimal or near optimal solutions to the NP-hard problem. Numerical examples show that this model leads to an appropriate compromise between system configuration costs and expected material handling costs to meet the varying product demands. These example problems also show that the proposed algorithm is effective and computationally efficient for small or medium size problems.     

A close neighbour algorithm for designing cellular manufacturing systems

The first step in creating a cellular manufacturing system is to identify machine groups and form part families. Clustering and data organization (CDR) algorithms (such as the bond energy algorithm) and array sorting (ARS) methods (such as the rank order clustering algorithm) have been proposed to solve the machine and part grouping problem. However, these methods do not always produce a solution matrix that has a block diagonal structure, making visual identification of machine groups and part families extremely difficult. This paper presents a ‘close neighbour algorithm’ to solve this problem. The algorithm overcomes many deficiencies of the CDR and ASM methods. The algorithm is tested against ten existing algorithms in solving test problems from the literature. Test results show that the algorithm is very reliable and efficient.     

Design of cellular manufacturing system with quasi-dynamic dual resource using multi-objective GA

A new concept is presented in this paper of quasi-dynamic cell formation for the design of a cellular manufacturing system, based on analysing the fact that static and dynamic cell formation could not reflect the real situation of a modern cellular manufacturing system. Further, workforce resources are integrated into quasi-dynamic cell formation and thus a quasi-dynamic dual-resource cell-formation problem is proposed. For solving this problem, this paper first establishes a non-linear mixed integer programming model, where inter-cell and intra-cell material cost, machine relocation cost, worker operation time, loss in batch quality and worker salary are to be minimised. Then, a multi-objective GA is developed to solve this model. Finally, a real life case study is conducted to validate the proposed model and algorithm. The actual operation results show that the case enterprise significantly decreases its material handling cost and workforce number and obviously increases its product quality after carrying out the obtained scheme.     

Cell formation using a Fuzzy Min-Max neural network

This paper proposes the application of a Fuzzy Min-Max neural network for part family formation in a cellular manufacturing environment. Once part families have been formed, a minimum cost flow model is used to form the corresponding machine cells. For simplicity, the input data are in the form of a binary part- machine incidence matrix, although the algorithm can work with an incidence matrix with continuous values. The application of Fuzzy Min-Max is interpreted in physical terms and compared with a related neural network applied previously for cell formation, the Fuzzy ART network. Both neural networks have similarities and differences that are outlined. The algorithms have been programmed and applied to a large set of problems from the literature. Fuzzy Min-Max generally outperforms Fuzzy ART, and the computational times are small and similar in both algorithms.     

Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect

This article addresses the no-wait flowshop scheduling problem with simultaneous consideration of common due date assignment, convex resource allocation and learning effect in a two machine setting. The processing time of each job can be controlled by its position in a sequence and also by allocating extra resource, which is a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the optimal common due date, the resource allocation and the schedule of jobs such that the total earliness, tardiness and common due date cost (the total resource consumption cost) are minimized under the constraint condition that the total resource consumption cost (the total earliness, tardiness and common due date cost) is limited. Polynomial time algorithms are developed for two versions of the problem.     

Algorithms for multiprocessor scheduling with machine release times

In this paper we present algorithms for the problem of scheduling n independent jobs on m identical machines. As a generalization of the classical multiprocessor scheduling problem each machine is available only at a machine dependent release time. Two objective functions are considered. To minimize the makespan, we develop a dual approximation algorithm with a worst case bound of 5/4. For the problem of maximizing the minimum completion time, we develop an algorithm, such that the minimum completion time in the schedule produced by this algorithm is at least 2/3 times the minimum completion time in the optimum schedule. The paper closes with some numerical results.     

Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity

In this paper, we consider common due-window assignment and scheduling problems with general position-dependent processing times involving deteriorating and compressible maintenance activity on a single machine. Two models associated with maintenance activity are examined in this article, in which the maintenance length is assumed to be either time-dependent and compressible or position-dependent and compressible. The objective is to find jointly the location and size of due-window, position of maintenance as well as resource amount allocated to it, and job sequence to minimise a total cost function based on earliness, tardiness, window location, window size and resource cost. We show that the problem considered in each of the two models’ setting can be optimally solved with polynomial time algorithm by reducing to assignment problem. Finally, two examples are provided to illustrate the solution procedures.