Coordinated scheduling of a single machine with sequence-dependent setup times and time-window constraints

In this paper we consider the selection and scheduling of several jobs on a single machine with sequence-dependent setup times and strictly enforced time-window constraints on the start times of each job. We demonstrate how to develop network-based algorithms to sustain the desired work in process (WIP) profile in a manufacturing environment. Short-term production targets are used to coordinate decentralised local schedulers and to make the objectives of specific areas in line with the chain objectives. A wide range of test problems with two different network structures are simulated. The effectiveness, efficiency, and robustness of the proposed algorithms are analysed and compared with an exhaustive search approach.     

Scheduling a flow-line manufacturing cell: a tabu search approach

The performance of two heuristic procedures for the scheduling of a flow-line manufacturing cell was compared. We propose a procedure based on a combinatorial search technique known as tabu search. The new procedure is compared with a heuristic based on simulated annealing which was proposed in earlier research. The scheduling problem addressed here differs from the traditional flow-shop scheduling problem in the sense that we are interested in sequencing part families (i.e. groups of jobs which share a similar setup) as well as individual jobs within each family. The results reveal that the tabu search heuristic outperforms the simulated annealing heuristic by generating 'better solutions' in less computation time.     

Continuous-time algorithms for scheduling a single machine with sequence-dependent setup times and time window constraints in coordinated chains

In this paper we address the problem of selecting and scheduling several jobs on a single machine with sequence-dependent setup times and strictly enforced time window constraints on the start time of each job. We use short-term production targets to coordinate decentralised local schedulers and to make the objectives of specific areas in line with the chain objectives by maintaining a desired work in process profile in manufacturing environments. The existing literature in this domain is based on discrete-time approaches. We depart from prior approaches by considering continuous time. We introduce a two-step mathematical programming model based on disjunctive constraints to solve small problems to optimality, and propose an insertion-based heuristic to solve large-scale instances. We provide several variations of the insertion heuristic based on different score functions. The primary objective of these approaches is to maximise the total defined score for jobs while satisfying production targets for families of jobs in each shift. Further, our models minimise the maximum completion time of all selected jobs. The effectiveness, efficiency, and robustness of the proposed algorithms are analysed and compared with the existing literature.     

A general framework for scheduling equipment and manpower at container terminals

In this paper, we propose a general model for various scheduling problems that occur in container terminal logistics. The scheduling model consists of the assignment of jobs to resources and the temporal arrangement of the jobs subject to precedence constraints and sequence-dependent setup times. We demonstrate how the model can be applied to solve several different real-world problems from container terminals in the port of Hamburg (Germany). We consider scheduling problems for straddle carriers, automated guided vehicles (AGVs), stacking cranes, and workers who handle reefer containers. Subsequently, we discuss priority rule based heuristics as well as a genetic algorithm for the general model. Based on a tailored generator for experimental data, we examine the performance of the heuristics in a computational study. We obtain promising results that suggest that the genetic algorithm is well suited for application in practice.     

Reducing tardy jobs by integrating process planning and scheduling functions

This paper presents a dynamic approach to reduce tardy jobs through the integration of process planning and scheduling in a batch-manufacturing environment. The developed method aims at re-generating a schedule with fewer tardy jobs, step by step, by exploring the process plan solution space of the tardy jobs. The integrated system comprises a process planning module, a scheduling module, and an integrator module. The process planning module employs an optimisation approach in which the entire plan solution space is first generated and a search algorithm is then used to find the optimal plan, while the scheduling module is based on commonly used heuristics. Based on the job tardiness information of the generated schedule, the integrator module automatically issues a modification order to the process plan solution space of the tardy jobs. The process planning and scheduling modules are then re-run to generate a new plan/schedule solution. Through this iterative process, a satisfactory schedule can be gradually achieved. The uniqueness of this approach is characterised by the flexibility of the process planning strategy, which makes full use of the plan solution space intuitively to achieve a satisfactory schedule. Several examples are presented to confirm the efficacy and the effectiveness of the developed integration system.     

A genetic search algorithm to optimize job sequencing under a technological constraint in a rolling-mill facility

This article presents some results from the application of a genetic search algorithm to solve a job scheduling problem where setup costs depend on the order of the jobs. An empirical study shows that, for small problems, the solutions given by the genetic algorithm are as good as those obtained with a mixed-integer linear program. For larger problems that are computationally infeasible, we benchmark the genetic solutions against traditional scheduling heuristics. We also study different population management strategies that can improve the performance of the algorithm. Finally, future research avenues are discussed.     

Neighbourhood search meta-heuristics for capacitated lot-sizing with sequence-dependent setups

We address a problem that often arises in industry, the multi-item capacitated-lot-sizing and scheduling problem with sequence-dependent setup times and costs. Powerful commercial solvers fail to solve even medium-sized instances of this NP-hard problem, therefore we employ a tabu search and a variable neighbourhood search meta-heuristic to solve it and compare the performance of these meta-heuristics over time. In contrast to the majority of the literature on this topic, the solution representation explicitly considers production quantities and setup variables, which enables us to develop fast search heuristics. A comprehensive set of computational experiments shows the effectiveness and efficiency of the proposed approaches in solving medium- to large-sized problems.     

Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times

This paper focuses on an identical parallel machine scheduling problem with minimising total tardiness of jobs. There are two major issues involved in this scheduling problem; (1) jobs which can be split into multiple sub-jobs for being processed on parallel machines independently and (2) sequence-dependent setup times between the jobs with different part types. We present a novel mathematical model with meta-heuristic approaches to solve the problem. We propose two encoding schemes for meta-heuristic solutions and three decoding methods for obtaining a schedule from the meta-heuristic solutions. Six different simulated annealing algorithms and genetic algorithms, respectively, are developed with six combinations of two encoding schemes and three decoding methods. Computational experiments are performed to find the best combination from those encoding schemes and decoding methods. Our findings show that the suggested algorithm provides not only better solution quality, but also less computation time required than the commercial optimisation solvers.     

A hybrid flowshop scheduling problem for a cold treating process in seamless steel tube production

Seamless steel tubes often have various categories and specifications, which further require complicated operations in production, especially in the cold treating process (CTP). This paper investigates the scheduling problem using the seamless tube plant of Baoshan Iron and Steel Complex as a study background. By considering the practical production constraints such as sequence-dependent setup times, maintenance schedule, intermediate material buffers, job-machine matches, we formulate the hybrid flowshop scheduling problem with a non-linear mixed integer programming model (NMIP). In addition, our model provides a flexibility to remove the permutation assumption, which is often a limitation in early studies. In order to obtain the solution of the above NMIP problem, a two-stage heuristic algorithm is proposed and it combines a modified genetic algorithm and a local search method. With real production instances, our computation experiments indicate that the proposed algorithm is efficient and it outperforms several other approaches. Industrial implementation also shows that such a scheduling tool brings a cost saving of more than 10% and it substantially reduces the computation time. Our study also illustrates the need of relaxing permutation assumption in such a scheduling problem with complicated operation sequences.     

A Meta-RaPS for the early/tardy single machine scheduling problem

This paper investigates a meta-heuristic solution approach to the early/tardy single machine scheduling problem with common due date and sequence-dependent setup times. The objective of this problem is to minimise the total amount of earliness and tardiness of jobs that are assigned to a single machine. The popularity of just-in-time (JIT) and lean manufacturing scheduling approaches makes the minimisation of earliness and tardiness important and relevant. In this research the early/tardy problem is solved by Meta-RaPS (meta-heuristic for randomised priority search). Meta-RaPS is an iterative meta-heuristic which is a generic, high level strategy used to modify greedy algorithms based on the insertion of a random element. In this case a greedy heuristic, the shortest adjusted processing time, is modified by Meta-RaPS and the good solutions are improved by a local search algorithm. A comparison with the existing ETP solution procedures using well-known test problems shows Meta-RaPS produces better solutions in terms of percent difference from optimal. The results provide high quality solutions in reasonable computation time, demonstrating the effectiveness of the simple and practical framework of Meta-RaPS.     

Unrelated parallel machine scheduling with job splitting

Scheduling jobs on unrelated parallel machines is an activity that is very much a part of industrial scheduling. We report a methodology for minimizing the total weighted tardiness of all jobs intended to be processed on unrelated parallel machines in the presence of dynamic job releases and dynamic machine availability. More importantly, the mixed (binary) integer linear programming model formulated for the problem incorporates a couple of “hard” operational constraints to ensure that just-in-time manufacturing practices are followed by controlling the work-in-process and/or finished goods inventories generated by split jobs mandated by a tight due date, a high priority, and/or a high workload. Four different methods based on simple and composite dispatching rules are used to identify an initial solution, which is then used by the tabu-search-based heuristic solution algorithm to ultimately find the best solution. Incorporating the various tabu search features led to the development of six different heuristics that were tested on eight small problem instances to compare the quality of their solutions to the optimal solutions. The results show that the proposed heuristics are capable of obtaining solutions of good quality in a remarkably short computation time with the best performer among them recording a percentage deviation of only 1.18%. A factorial experiment based on a split-plot design is performed to test the performance of the heuristics on problem structures, ranging from nine jobs and three machines to 60 jobs and 15 machines. The results show that the newly developed composite dispatching heuristic, referred to as the modified apparent tardiness cost, is capable of obtaining initial solutions that significantly accelerate the tabu-search-based heuristics to attain the best solution. The use of a long-term memory function is proven to be advantageous in solving all problem structures. In addition, the variable tabu list size is preferred for solving the small problem structure, while the fixed tabu list size is preferred as the problem size grows from small to medium and then large.     

Single-machine scheduling with sequence dependent setup to minimize total weighted squared tardiness

This paper addresses the NP-hard problem of scheduling N independent jobs on a single machine with release dates, due dates, sequence dependent setup times, and no preemption where the objective is to minimize the weighted sum of squared tardiness. A Lagrangian relaxation based approach is developed for single-machine scheduling with sequence dependent setup times that is based on a list scheduling concept in conjunction with Lagrangian relaxation. Sequence dependent setup times are formulated as capacity constraints, and then are relaxed using Lagrangian multipliers. The primal problem is decomposed into job-level subproblems which are solved optimally and an approximate dual problem is then solved using a sub-gradient technique. The result of the relaxation is a list of jobs sequenced by beginning times that is then improved via a three-way swap. Experimental results are compared with EDD (Earliest Due Date) and ATCS (Apparent Tardiness Cost with Setups) dispatching rules, a four-way swap local search, tabu search, and simulated annealing. The adopted approach results in superior solution quality with respect to EED, ATCS, four-way swap, and tabu search results. It has comparable solution quality to the simulated annealing results, but is substantially more computationally efficient. Overall, the approach is capable of dealing with realistically sized single machine scheduling problems with release dates, due dates, and sequence dependent setup times.     

Maximising profit for multiple-product,single-period,single-machine manufacturing under sequential set-up constraints that depend on lot size

The classical problem of order acceptance/rejection in make-to-order environments, when aiming to maximise profit with machine set-ups is extended in this paper to multiple set-ups depending on manufacturing batch size. In this case, if the manufacturing batch is larger than certain product-dependent bounds, not only is the initial set-up required but also periodic reset-ups are in order, generating sub-batches of the same order, such as tool resharpening and machine recalibration. A network formulation provides the basis for identifying effective algorithms to obtain a solution to the problem. A binary programming model (BPM) and a dynamic programming formulation (DPF) are proposed to solve the problem to optimality. In addition, two heuristics are developed to obtain lower bounds on maximum profit: each attempt to maximise customer satisfaction under production time restrictions, and to provide an extension to the classical knapsack problem. Numerical experimentation shows that computational time is not an issue when BPM and heuristics are applied, but the cost of commercial solvers for BPM algorithms might be problematic. However, if the aim is to code the DPF in-house, the curse of dimensionality in dynamic programming must be addressed, although dynamic programming does yield a full sensitivity analysis, which is useful for decision-making.     

A genetic algorithm based approach for scheduling of jobs containing multiple orders in a three-machine flowshop

This paper investigates a new scheduling problem of multiple orders per job (MOJ) in a three-machine flowshop consisting of an item-processing machine, a lot-processing machine and a batch-processing machine, for a semiconductor manufacturing operation that must form a layer on the wafers. The three-machine flowshop MOJ scheduling problem deals with sequencing customer orders, assigning orders to jobs, and then combining the formed jobs into batches. Genetic algorithms are presented for this scheduling problem to minimise the total weighted tardiness (TWT), in the presence of non-zero order ready times, different order due dates, different order weights and unequal order sizes. Extensive experiments were performed to compare the proposed genetic algorithm (GA)-based approach with the benchmark heuristics presented in previous studies. The experiments led to the conclusions that the GA-based approach is significantly superior over other heuristics in terms of TWT and can find near-optimal solutions in an acceptable amount of computation time.     

An iterated beam search algorithm for the multi-level production smoothing problem with workload smoothing goal

This paper is concerned with a generalised version of the production smoothing problem. The problem involves both usage and loading goals at multiple levels. Three existing heuristic approaches, namely the one-stage (1SH), two-stage (2SH) and earliest-due-date (EDD) heuristics are adapted, as well as a novel iterated beam search (IBS) algorithm is proposed to solve the problem. An extensive computational study is designed in the paper and used to compare the four heuristic approaches. The results show that IBS finds the best solution in the majority of test instances and requires less computation time than 2SH.     

Towards robustness of response times: minimising the maximum inter-completion time on parallel machines

Motivated by scheduling practices that require a response to unplanned high-priority jobs as soon as possible without preempting any in-processing jobs, this paper considers a deterministic identical parallel machine scheduling problem to achieve robustness with regard to a worst-case response time. To the best of our knowledge, this paper is the first to study the objective of minimising the maximum inter-completion time, i.e. the maximum time difference between any two consecutive completion times of jobs. For this novel scheduling problem, we first show its NP-hardness, and then propose an integer linear programming formulation and three heuristic approaches. Numerical experiments demonstrate the efficiency of our solution methods.     

Batch scheduling problem for a machinery factory with fixed-position layout

We consider a batch scheduling problem for a two-stage flow shop with fixed-position layout. In the first stage, a fixed number of jobs are assembled on a batch machine with a family batch setup time and a common processing time. In the second stage, the assembled jobs are individually performed for system integration on a discrete machine. The finished job is immediately packed and shipped if the payment has been made; otherwise, it is moved to a temporary storage area, incurring additional removal time. This study develops a mixed integer programming (MIP) to solve the problem of minimising the total completion time and proposes two heuristics for large-size problems. Computational results show that the proposed methods can be applied to resolve real-world problems similar to those in this study.     

Scheduling a permutation flow shop with family setups to minimise total tardiness

This paper presents several procedures for scheduling a permutation flow shop with family setups when the objective is to minimise total tardiness. These procedures are tested on several problem sets with varying numbers of families, jobs, and machines, three setup time distributions, and various levels of due date tightness and variability. The results show that variable greedy algorithms are effective when solving small problems, but a neighbourhood search procedure that includes searches with a neighbourhood defined by the sequence of batches of jobs belonging to the same setup family is more effective when solving large problems. Results are also presented, showing that significant reductions in total tardiness can be obtained if the time required to perform the family setups is reduced.     

Heuristics and sequence-dependent set-up jobs in flow line cells

A key operational issue in cellular manufacturing systems is the scheduling of jobs within a family at each cell. Sequence-dependent set-up times during changeovers from one job to another afford scope for the exploitation of similarities at this stage to minimize the time spent on set-ups. This paper proposes heuristics for scheduling jobs within a part family by identifying subfamilies and sequencing them to improve the use of machines within a cell and to reduce the tardiness as well as the number of tardy jobs. The proposed heuristic, when evaluated by comparison with existing benchmark heuristics, yielded encouraging results.     

Scheduling a dynamic flexible flow line with sequence-dependent setup times: a simulation analysis

This paper presents a simulation-based experimental study of scheduling rules for scheduling a dynamic flexible flow line problem considering sequence-dependent setup times. A discrete-event simulation model is presented as well as eight adapted heuristic algorithms, including seven dispatching rules and one constructive heuristic, from the literature. In addition, six new proposed heuristics are implemented in the simulation model. Simulation experiments are conducted under various conditions such as setup time ratio and shop utilisation percentage. One of the proposed rules performs better for the mean flow time measure and another one performs better for the mean tardiness measure. Finally, multiple linear regression based meta-models are developed for the best performing scheduling rules.