A P-invariant-based algorithm for simple assembly line balancing problem of type-1

A simple assembly line balancing problem of type-1 (SALBP-1) concerns minimizing the number of workstations on an assembly line for a given cycle time. In this problem only a single product with deterministic task times is considered. Since the SALBP-1 is known as an NP-hard, considerable research effort has been spent to develop heuristic approaches. In this study we develop a different heuristic approach based on the P-invariants of Petri nets. The algorithm is coded in MATLAB, and its efficiency is tested on Talbot’s and Hoffmann’s benchmark datasets according to some performance measures and classifications. A computational study validates its effectiveness on Tonge’s 70-task problem by comparison with solutions of traditional heuristics and a genetic algorithm reported to perform well.     

mAOR: A heuristic-based reactive repair mechanism for job shop schedules

Literature on job shop scheduling has primarily focused on the development of predictive schedules that generate an allocation sequence of jobs on machines. However, in practice, frequent deviations from a predictive schedule occur when the job shop experiences either external (e.g. unexpected arrival of urgent jobs) or internal disturbances (e.g. machine breakdowns) and renders the schedules inefficient. The reactive repair of the original schedule is a better alternative to total rescheduling, as the latter is not only time consuming but also leads to shop floor nervousness. Most of the existing schedule repair heuristics handle singular disruptions only. In this paper, the typical job shop disruptions are studied and their repair processes are decomposed into four generic repair steps, which are achieved using the proposed modified AOR (mAOR) heuristic. An extensive simulation study has also been conducted to evaluate the performance of the mAOR schedule repair heuristic, and the results indicate that the mAOR heuristic is effective in repairing job shop schedules when faced with disruptions.     

Scheduling algorithms for two-stage reentrant hybrid flow shops: minimizing makespan under the maximum allowable due dates

We consider the scheduling problem in hybrid flow shops that consist of two stages in series, each of which has multiple identical parallel machines. Each job has reentrant flow, i.e., the job visits each production stage several times. The problem is to determine the allocation of jobs to machines as well as the sequence of the jobs assigned to each machine for the objective of minimizing makespan subject to the maximum allowable due dates in the form of a constraint set with a certain allowance. To solve the problem, two types of algorithms are suggested: (a) a branch and bound algorithm that gives optimal semi-permutation schedules; and (b) heuristic algorithms that give non-permutation schedules. To show their performances, computational experiments were done on a number of test problems and the results are reported. In particular, one of the heuristics is competitive to the branch and bound algorithm with respect to the solution quality while requiring much shorter computation times.     

Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date are given. The preemption of jobs is not permitted. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Firstly, several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. Then, genetic algorithms are suggested. We discuss the components of these algorithms and test their parameters. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages.     

Greedy randomised dispatching heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties

In this paper, we present greedy randomised dispatching heuristics for the single-machine scheduling problem with quadratic earliness and tardiness costs and no machine idle time. The several heuristic versions differ, on the one hand, on the strategies involved in the construction of the greedy randomised schedules. On the other hand, these versions also differ on whether they employ only a final improvement step or perform a local search after each greedy randomised construction. The proposed heuristics were compared with existing procedures as well as with optimum solutions for some instance sizes. The computational results show that the proposed procedures clearly outperform their underlying dispatching heuristic, and the best of these procedures provide results that are quite close to the optimum. The best of the proposed algorithms is the new recommended heuristic for large instances as well as a suitable alternative to the best existing procedure for the larger of the middle-sized instances.     

Comparative Evaluations of Buffer Allocation Strategies in a Serial Production Line

The problem of allocating buffer storage to serial production lines so as to maximise steady-state throughput is considered. Some researchers have previously developed rules of thumb for the optimum allocation of a given total amount of buffer space to maximise the throughput of a production line. In this paper, a modified buffer allocation strategy based on the Lin & Lin’s rule, is suggested, and it is compared with three other existing strategies. Some recommendations are made on how to select a buffer allocation strategy. In addition, a buffer utilisation-based search method, which is a methodology to increase the throughput of a production line, is suggested.     

A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem

Flow-shop scheduling problem (FSP) deals with the scheduling of a set of jobs that visit a set of machines in the same order. The FSP is NP-hard, which means that there is no efficient algorithm to reach the optimal solution of the problem. To minimize the make-span of large permutation flow-shop scheduling problems in which there are sequence-dependent setup times on each machine, this paper develops one novel hybrid genetic algorithms (HGA). Proposed HGA apply a modified approach to generate the population of initial chromosomes and also use an improved heuristic called the iterated swap procedure to improve them. Also the author uses three genetic operators to make good new offspring. The results are compared to some recently developed heuristics and computational experimental results show that the proposed HGA performs very competitively with respect to accuracy and efficiency of the solutions.     

No-wait flowshop scheduling problem to minimize the number of tardy jobs

This research addresses the m-machine no-wait flowshop scheduling problem with the objective of minimizing the number of tardy jobs. The problem is known to be NP-hard even for the two machines, and literature reveals that no heuristics have been developed for this problem. In this paper, we propose an efficient heuristic based on simulated annealing, where we first adapt the single-machine optimal algorithm to our problem to develop two new heuristics, NOTA and NOTM. An improved simulated annealing heuristic, called SA-GI, is then developed by feeding the best performing heuristic among NOTA, NOTM, and EDD into the simulated annealing algorithm. A second proposed heuristic, called SA-IP, further improves the SA-GI solution by using insertion and pair-wise exchange techniques. Based on the computational experiments, the overall relative percentage errors of the heuristic SA, SA-GI, and SA-IP are 8.848, 8.428, and 0.207, respectively. The computational times of the three heuristics are close to each other, and the largest average time is less than one second, and hence, the computational time is not an issue. Therefore, the heuristic SA-IP is the best one.     

Heuristic search algorithms for lot streaming in a two-machine flowshop

The objective of this paper is to propose and evaluate heuristic search algorithms for a two-machine flowshop problem with multiple jobs requiring lot streaming that minimizes makespan. A job here implies many identical items. Lot streaming creates sublots to move the completed portion of a production lot to second machine. The three heuristic search algorithms evaluated in this paper are Baker’s approach (Baker), genetic algorithm (GA) and simulated annealing (SA) algorithm. To create neighborhoods for SA, three perturbation schemes, viz., pair-wise exchange, insertion and random insertion are used, and the performance of these on the final schedule is also compared. A wide variety of data sets is randomly generated for comparative evaluation. The parameters for GA and SA are obtained after conducting sensitivity analysis. The genetic algorithm is found to perform well for lot streaming in the two-machine flowshop scheduling.     

Heuristical job allocation in a flexible manufacturing system

Two heuristic algorithms are presented for solving the scheduling problem in a statically loaded Flexible Manufacturing System (FMS). The heuristics goal is to minimise the total cost resulting from the tardiness of jobs. Using the same heuristics, an iterative method is proposed to find an optimal makespan and the average lead time. Modifications required to handle the case of a dynamically loaded FMS are then presented. Simulation results show that the developed heuristics appear to out perform the other published techniques used in obtaining the schedules associated with minimum makespan, minimum average lead time and minimum cost of tardiness. Finally, the simulation of the dynamic case shows that the algorithms could be implemented locally on each station for the scheduling calculation.     

Algorithms for the single machine total weighted completion time scheduling problem with release times and sequence-dependent setups

This paper considers the problem of scheduling n jobs on a single machine to minimize the total weighted completion time in the presence of sequence-dependent setup times and release times. To the best of our knowledge, little research has been devoted to this scheduling problem. Therefore, we developed two exact algorithms, including a constraint programming model and a branch-and-bound method for small problems. The obtained optimal solutions can be used as a benchmark for evaluating the performance of heuristics. With the complexity in mind, two heuristics, including a best index dispatch (BID) and a modified weighted shortest processing time (MWSPT) based on non-delay concepts are also proposed for large problems. The time complexities of the two proposed heuristics are O(n ⁴) and O(n ³), respectively. The computational results showed that the branch-and-bound method could solve most instances with 40 jobs under the time limit of 7,200 s. The BID heuristic is superior to the MWSPT in solution quality, although both can efficiently and effectively obtain near-optimal solutions for large instances.     

Sequencing and scheduling of job and tool in a flexible manufacturing cell

Flexible manufacturing cells (FMCs) are now common place in many manufacturing companies, due to their numerous advantages such as the production of a wide range of part types with short lead times, low work-in-progress, economical production of small batches and high resource utilization. Part and tool flows, two major dynamic entities, are the key factors and their management plays an important role in the operation of a FMC. The theme of this paper is to a generate joint operation - tool schedule in a FMC consisting of several machines and a common tool magazine (CTM). To achieve this aim, the jobs and tools must be jointly sequenced and scheduled in a tool constrained environment. Two heuristic algorithms, priority dispatching rules algorithm (PDRA) and simulated annealing algorithm (SAA) are proposed to derive optimal solutions. PDRA, are the most frequently applied heuristics for solving job shop/combinatorial scheduling problems in practice because of their ease of implementation and their low complexity, when compared with excel algorithms. SAA that belong to search categories, which are emerging along with the high computational capability of computers, can be used for FMS scheduling problems. Both adopt the Giffler & Thompson procedure for active feasible schedule generation. The performance of these two algorithms is compared with makespan and computational time. The analysis reveals that the SAA based heuristic provides an optimal or near optimal solution with reasonable computational time.     

A numerical study on the spray-to-spray impingement system

The present article aims to perform numerical calculations for inter-spray impingement of two diesel sprays under a high injection pressure and to propose a new hybrid model for droplet collision on the basis of literature findings. The hybrid model is compared with the original 0’ Rourke’s model, which has been widely used for spray calculations. The main difference between the hybrid model and the O’Rourke’s model is mainly in determination of the collision threshold condition, in which the preferred directional effect of droplets and a critical collision radius are included. The Wave model involving the cavitation effect inside a nozzle is used for predictions of atomization processes. Numerical results are reported for different impingement angles of 60° and 90° in order to show the influence of the impinging angle on spray characteristics and also compared with experimental data. It is found that the hybrid model shows slightly better agreement with experimental data than the O’Rourke’s model.     

Further study of minimizing total flowtime for the worker assignment scheduling problem in the identical parallel-machine models

Previously, minimizing total flow time in the model of an identical, parallel machines with nonpreemptive jobs has been investigated. Because the specific problem has been shown as NP-complete, heuristics have been developed for solving it. A shortest processing time for A_i part (SPT-A) heuristic is used for the job scheduling subproblem. In addition, the largest marginal contribution (LMC) procedure is used for the worker assignment subproblem and then minimizes the total flow time. Different values of W (number of workers) are used for further study of the performance of these heuristics developed. In conclusion, for the simplified processing time function, values of W have no significant influence when the heuristics are applied. In other words, no matter what value of W was used when SPT rule was applied, the heuristics generate the same, excellent results.     

A heuristic method for the combined location routing and inventory problem

The combined location routing and inventory problem (CLRIP) is used to allocate depots from several potential locations, to schedule vehicles’ routes to meet customers’ demands, and to determine the inventory policy based on the information of customers’ demands, in order to minimize the total system cost. Since finding the optimal solution(s) for this problem is a nonpolynomial (NP) problem, several heuristics for searching local optima have been proposed. However, the solutions for these heuristics are trapped in local optima. Global search heuristic methods, such as tabu search, simulated annealing method, etc., have been known for overcoming the combinatorial problems such as CLRIP, etc. In this paper, the CLRIP is decomposed into two subproblems: depot location-allocation problem, and routing and inventory problem. A heuristic method is proposed to find solutions for CLRIP. First of all, an initial solution for CLRIP is determined. Then a hybrid heuristic combining tabu search with simulated annealing sharing the same tabu list is used to improve the initial solution for each subproblem separately and alternatively. The proposed heuristic method is tested and evaluated via simulation. The results show the proposed heuristic method is better than the existing methods and global search heuristic methods in terms of average system cost.     

Heuristics for assembly operation scheduling problem in flexible assembly systems

In this paper we address the problem of scheduling n assembly operations with in-tree constraints on m unrelated parallel workstations in flexible assembly systems, which we call the assembly operation scheduling problem (AOSP). No preemption of assembly operations is allowed and the primary objective is to minimize the maximum completion time. This problem is equivalent to R|tree|C_max. For this notorious NP-hard problem, four heuristic algorithms including decomposition (DECOMP), earliest completion time (ECT), shortest processing time (SPT), and earliest starting time(EST) heuristic are proposed and their performances are comparatively investigated. DECOMP uses a decomposition technique to practically solve this problem. The assembly operation tree is decomposed and then AOSP is reduced to a set of subproblems of R||C_max and R,r_j|r_i|C_max. Two efficient heuristics were proposed for the reduced subproblems. The other three heuristics basically use the machine selection rules to determine the machine for processing the current operation. Of these heuristics, DECOMP showed the best performance in terms of quality of schedule. Computational results show that all the proposed algorithms except the EST heuristic perform quite well in terms of both quality of solution and computation time.     

An efficient heuristic for total flowtime minimisation in no-wait flowshops

In this paper, we address the problem of scheduling jobs in a no-wait flowshop with the objective of minimising the total completion time. This problem is well-known for being nondeterministic polynomial-time hard, and therefore, most contributions to the topic focus on developing algorithms able to obtain good approximate solutions for the problem in a short CPU time. More specifically, there are various constructive heuristics available for the problem [such as the ones by Rajendran and Chaudhuri (Nav Res Logist 37:695–705, 1990); Bertolissi (J Mater Process Technol 107:459–465, 2000), Aldowaisan and Allahverdi (Omega 32:345–352, 2004) and the Chins heuristic by Fink and Voβ (Eur J Operat Res 151:400–414, 2003)], as well as a successful local search procedure (Pilot-1-Chins). We propose a new constructive heuristic based on an analogy with the two-machine problem in order to select the candidate to be appended in the partial schedule. The myopic behaviour of the heuristic is tempered by exploring the neighbourhood of the so-obtained partial schedules. The computational results indicate that the proposed heuristic outperforms existing ones in terms of quality of the solution obtained and equals the performance of the time-consuming Pilot-1-Chins.     

Optimal Method of Capacitated Lot-Sizing Planning in Manufacturing Systems

This paper analyzes the capacitated lot-sizing problem considering an individual machine’s production capacity using a two-layer hierarchical method to minimize the sum of the dynamic inventory cost and the overtime penalty cost. The genetic algorithm, the parameter linear programming method, and a heuristic method were used in the developed method. The method uses the genetic operator to define the lot-sizing matrix (the first layer), linear programming to determine each machine's schedule (the second layer) according to the lot-sizing matrix, and the heuristic method to verify the feasibility of the solutions by adjusting them to meet the constraint requirements. The scheduling of machines in a press shop demonstrates the effectiveness of the algorithm. The result shows that the algorithm is convergent. Translated from J. Tsinghua Univ. (Sci. Tech.), 2004, 44(5)     

A pattern-directed approach to flexible manufacturing: A framework for intelligent scheduling, learning, and control

The planning, scheduling, and control of manufacturing systems can all be viewed as problem-solving activities. In flexible manufacturing systems (FMSs), the computer program carrying out these problem-solving activities must additionally be able to handle the shorter lead time, the flexibility of job routing, the multiprocessing environment, the dynamic changing states, and the versatility of machines. This article presents an artificial intelligence (AI) method to perform manufacturing problem solving. Since the method is driven by manufacturing scenarios represented by symbolic patterns, it is referred to as pattern-directed. The method is based on three AI techniques. The first is the pattern-directed inference technique to capture the dynamic nature of FMSs. The second is the nonlinear planning technique to construct schedules and assign resources. The third is the inductive learning method to generate the pattern-directed heuristics. This article focuses on solving the FMS scheduling problem.In addition, this article reports the computation results to evaluate the utility of various heuristic functions, to identify important design parameters, and to analyze the resulting computational performance in using the pattern-directed approach for manufacturing problem-solving tasks such as scheduling.     

Production planning of a flexible manufacturing system in a material requirements planning environment

Early flexible manufacturing system (FMS) production planning models exhibited a variety of planning objectives; typically, these objectives were independent of the overall production environment. More recently, some researchers have proposed hierarchical production planning and scheduling models for FMS. In this article, we examine production planning of FMS in a material requirements planning (MRP) environment. We propose a hierarchical structure that integrates FMS production planning into a closed-loop MRP system. This structure gives rise to the FMS/MRP rough-cut capacity planning (FMRCP) problem, the FMS/MRP grouping and loading (FMGL) problem, and the FMS/MRP detailed scheduling problem.We examine the FMRCP and FMGL problems in detail and present mathematical programming models for each of these problems. In particular, the FMRCP problem is modeled as a generalized assignment problem (GAP), and a GAP-based heuristic procedure is defined for the problem. We define a two-phase heuristic for the FMGL problem and present computational experience with both heuristics. The FMRCP heuristic is shown to solve problems that exhibit a dependent-demand relation within the FMS and with FMS capacity utilization as high as 99 percent. The FMGL heuristic requires very little CPU time and obtains solutions to the test problems that are on average within 1.5 percent of a theoretical lower bound.This FMS/MRP production planning framework, together with the resulting models, constitutes an important step in the integration of FMS technology with MRP production planning. The hierarchical planning mechanism directly provides for system-level MRP planning priorities to induce appropriate production planning and control objectives on the FMS while simultaneously allowing for necessary feedback from the FMS. Moreover, by demonstrating the tractability of the FMRCP and FMGL problems, this research establishes the necessary groundwork upon which to explore systemwide issues pertaining to the coordination of the hierarchical structure.