New scheduling algorithms and digital tool for dynamic permutation flowshop with newly arrived order

The permutation flowshop scheduling problem has been widely studied under static environment by assuming machines and jobs are available at the time of zero. However, in reality, new orders arrive at production systems randomly, which leads to sheer complexity in scheduling due to the dynamic changes given various constraints of resources. Previous studies simply attach new orders directly after the existing schedule. Recent study shows mixing jobs of old and new orders could result in better scheduling solutions. But the heuristic algorithms are still lacking to implement the job mixing policy. To address this problem, a novel scheduling strategy is herein proposed by integrating match-up strategy and real-time strategy (MR) in order to make use of the remaining time before the old order due date. Based on the new MR strategy, eleven new heuristics are introduced with ten existing and one new priority rules. Computational results illustrate the effectiveness of the new heuristics. A digital tool is developed for ease of application of these heuristics, and it is validated by case studies.     

A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem

As the interest of practitioners and researchers in scheduling in a multi-factory environment is growing, there is an increasing need to provide efficient algorithms for this type of decision problems, characterised by simultaneously addressing the assignment of jobs to different factories/workshops and their subsequent scheduling. Here we address the so-called distributed permutation flowshop scheduling problem, in which a set of jobs has to be scheduled over a number of identical factories, each one with its machines arranged as a flowshop. Several heuristics have been designed for this problem, although there is no direct comparison among them. In this paper, we propose a new heuristic which exploits the specific structure of the problem. The computational experience carried out on a well-known testbed shows that the proposed heuristic outperforms existing state-of-the-art heuristics, being able to obtain better upper bounds for more than one quarter of the problems in the testbed.     

A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria

The problem of scheduling in flowshop and flowline-based manufacturing cell is considered with the bicriteria of minimizing makespan and total flowtime of jobs, The formulation of the scheduling problems for both the flowshop and the flowline-based manufacturing cell is first discussed. We then present the development of the proposed heuristic for flowshop scheduling. A heuristic preference relation is developed as the basis for the heuristic so that only the potential job interchanges are checked for possible improvement with respect to bicriteria, The proposed heuristic algorithm as well as the existing heuristic are evaluated in a large number of randomly generated large-sized flowshop problems. We also investigate the effectiveness of these heuristics with respect to the objective of minimizing total machine idletime. We then modify the proposed heuristic for scheduling in a cell, and evaluate its performance.     

Scheduling distributed flowshops with flexible assembly and set-up time to minimise makespan

The scheduling problems under distributed production or flexible assembly settings have achieved increasing attention in recent years. This paper considers scheduling the integration of these two environments and proposes an original distributed flowshop scheduling problem with flexible assembly and set-up time. Distributed production stage is deployed several homogeneous flowshop factories that process the jobs to be assembled into final products in the flexible assembly stage. The objective is to find a schedule, including a production subschedule for jobs and an assembly subschedule for products, to minimise the makespan. Such a scheduling problem involves four successive decisions: assigning jobs to production factories, sequencing jobs at every factory, designating an assembly machine for each product and sequencing products on each assembly machine. The computational model is first established, and then a constructive heuristic (TPHS) and two hybrid metaheuristics (HVNS and HPSO) are proposed. Numerical experiments have been carried out and results validate the algorithmic feasibility and effectiveness. TPHS can obtain reasonable solutions in a shorter time, while metaheuristics can report better solutions using more yet acceptable time. HPSO is statistically comparable yet less robust compared with HVNS for small-scale instances. For the large-scale case, HPSO outperforms HVNS on both effectiveness and robustness.     

Solving the n-job 3-stage flexible flowshop scheduling problem using an agent-based approach

In this paper, a general methodology of agent-based manufacturing systems scheduling, incorporating game theoretic analysis of agent cooperation is presented to solve the n-job 3-stage flexible flowshop scheduling problem. The flowshops are flexible in the sense that a job can be processed by any of the identical machines at each stage. Our objective is to schedule a set of n jobs so as to minimize the makespan. We perform error bound analysis using the lower bound estimates developed in the literature as a datum for comparing the agent-based scheduling solutions with other heuristic solutions. The results of the evaluation show that the agent-based scheduling approach outperforms existing heuristics for the majority of the testing problems.     

Two MILP models for the N × M SDST flowshop sequencing problem

This paper presents the derivation and evaluation of two new MILP models for the SDST flowshop sequencing problem. The first model, TS1, was derived directly from the assignment-problem-based MILP model for the regular flowshop that Stafford modified from the original Wagner three-machine all-integer model. The second model, TS2, combined the properties of model TS1 with the looser constraints approach of Srikar and Ghosh, as modified by Stafford and Tseng (model SG*). Three experiments were used to compare both new models to the SG* model. Both new models were found to use significantly less computation time than the SG* model, especially for problem sizes of 6 or more jobs and 5 or more machines. The TS1 model used significantly less computation time than the TS2 model, making it the current best MILP model in the SDST flowshop literature.     

A modified ant-colony optimisation algorithm to minimise the completion time variance of jobs in flowshops

In this work, the flowshop scheduling problem is considered with the objective of minimising the completion-time variance (CTV) of jobs, and an Ant Colony Optimisation (ACO) algorithm is presented. Two implementations of the Modified Ant Colony Optimisation algorithm (MACO-I and MACO-II) are proposed to solve the permutation flowshop scheduling problem. The proposed ant-colony-algorithm implementations have been tested on 90 benchmark flowshop scheduling problems. The solutions yielded by the proposed MACO implementations are compared with various algorithms and with the best CTV of jobs reported in the literature. The proposed MACO implementations are found to perform very well in minimising the chosen performance measure.     

Bottleneck-based heuristics to minimize tardy jobs in a flexible flow line with unrelated parallel machines

This paper develops new bottleneck-based heuristics with machine selection rules to solve the flexible flow line problem with unrelated parallel machines in each stage and a bottleneck stage in the flow line. The objective is to minimize the number of tardy jobs in the problem. The heuristics consist of three steps: (1) identifying the bottleneck stage; (2) scheduling jobs at the bottleneck stage and the upstream stages ahead of the bottleneck stage; (3) using dispatching rules to schedule jobs at the downstream stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage, and two decision rules are developed to schedule the jobs on the bottleneck stage. This new approach neatly overcomes the difficulty of determining feasible arrival times of jobs at the bottleneck stage. In order to evaluate the performance of the proposed heuristics, six well-known dispatching rules are examined for comparison purposes. Six factors are used to design 729 production scenarios, and ten test problems are generated for each scenario. Computational results show that the proposed heuristics significantly outperform all the well-known dispatching rules. An analysis of the experimental factors is also performed and several interesting insights into the heuristics are discovered.     

Batch-scheduling problems through the flowshop with both receiving and delivery just in time

In scheduling literature, the flowshop problem is usually concerned only with finding a processing order of jobs on each machine. However, this paper addresses flowshop batch-scheduling problems, that is, to determine batch sizes of parts with a common due date, and to schedule the resulting batches. We propose an objective for the problems that not only minimizes inventory but also provides for receiving material just in time and delivery just in time. A heuristic method to solve the problem is proposed. An example is also provided to show how the proposed method works.     

Optimal Scheduling in a Multistage Flowshop

The combinatorial approach to solve the n-job, .M-machine flowshop scheduling problem is examined. The mathematical developments of the Dudek-Teuton algorithm shown are correct and valid if correctly interpreted. However, the optimality conditions developed by these authors are too stringent and as such the combinatorial analysis for the flowshop scheduling problem is extended and an algorithm is proposed for the solution of the multistage flowshop scheduling problem, where the objective is to minimize a specified measure of total production cost and jobs have their associated start and stop lags.     

Hybrid flowshop scheduling with family setup time and inconsistent family formation

This research considers a hybrid flowshop scheduling problem where jobs are organised in families according to their machine settings and tools. The family setup time arises when a machine shifts from processing one job family to another. The problem is compounded by the challenges that the formation of job families is different in different stages and only a limited number of jobs can be processed within one setup. This type of problem is common in the production process of standard metal components. This paper aims to propose two approaches to solve this problem. One is a metaheuristic in the form of a genetic algorithm and the other is a heuristic. The proposed approaches are compared and contrasted against the two relevant metaheuristic and heuristic adapted from solving a generalised sequence-dependent setup flowshop problem. Comparative results indicate that the proposed genetic algorithm has better performance on minimising makespan and the heuristic is more effective on reducing family setup time.     

Job shop scheduling heuristics and frequency of scheduling

This paper presents a job scheduling problem. Two important aspects are included in the subsequent analysis. The first is the dynamic nature whereby new jobs arrive to be included intermittently through time. The second is the uncertainty, or error in estimating process times, and the likelihood of machine breakdown. An experiment is presented which shows the performance of a number of heuristics in the form of dispatching disciplines under different scheduling conditions which are determined by the scheduling period and the level of uncertainty in the process times and machine breakdowns. Various different measures of performance which could be of importance to management are considered. These include mean ratio of flow time to process time, mean queueing time, mean lateness, percentage of jobs late and net CPU times required to generate schedules in the simulation process.

Results are presented showing the relationship between the performance of the heuristics relative to the different measures and the rescheduling period. These are discussed in the more general managerial context.     

Minimizing total tardiness of orders with reentrant lots in a hybrid flowshop

This study focuses on a hybrid flowshop scheduling problem, in which there are serial stages, each with identical parallel machines. In the hybrid flowshop, each order is composed of multiple lots with the same due date, and each lot can be processed on any one of parallel machines at each stage. In addition, there are reentrant flows since lots of certain orders have to visit the stages twice. Heuristic algorithms are suggested for the scheduling problem with the objective of minimizing total tardiness of a given set of orders. In these algorithms, the list-scheduling method is employed, and lots are scheduled with priorities determined with a construction method. Computational experiments are performed on randomly generated test problems. Results show that the suggested algorithms perform better than well-known dispatching rules for various scheduling problems and an algorithm that is used in a real system.     

考虑急件到达的单机鲁棒调度方法

实际生产过程中经常会有急件到达。由于急件的优先级最高,其到达容易扰乱初始调度,使实际调度性能恶化,影响调度目标的实现。针对以总拖期为目标且带有释放时间的单机调度问题,研究了在有急件到达情况下的鲁棒调度方法,以降低急件对实际调度性能的影响。鉴于该调度问题是NP hard问题,根据工件释放时间和交货期的关系构造“金字塔”结构,获得该调度问题的占优性质。根据这些占优性质和急件到达特点,研究急件到达情景下的占优规则,据此求解急件到达情景下的占优调度集合,作为鲁棒调度的备选调度方案集合。提出了应对急件到达的鲁棒调度算法。给出仿真算例验证了算法的有效性,算例表明本文给出的鲁棒调度方法能有效避免急件到达造成实际调度性能的恶化。      

Multi-objective meta-heuristics to solve three-stage assembly flow shop scheduling problem with machine availability constraints

In this paper, a three-stage assembly flow shop scheduling problem with machine availability constraints is taken into account. Two objectives of minimising total weighted completion times (flow time) and minimising sum of weighted tardiness and earliness are simultaneously considered. To describe this problem, a mathematical model is presented. The problem is generalisation of three-machine flow shop scheduling problem and two-stage assembly flow shop scheduling problem. Since these problems are known to be NP-hard, the considered problem is also strongly NP-hard. Therefore, two multi-objective meta-heuristics are presented to efficiently solve this problem in a reasonable amount of time. Comprehensive computational experiments are performed to illustrate the performance of the presented algorithms.     

A computational study of heuristics for two-stage flexible flowshops

We consider the scheduling of two-stage flexible flowshops. This manufacturing environment involves two machine centres representing two consecutive stages of production. Each machine centre is composed of multiple parallel machines. Each job has to be processed serially through the two machine centres. In each machine centre, a job may be processed on any of the machines. There are n independent jobs to be scheduled without preemption. The jobs can wait in between the two machine centres and the intermediate storage is unlimited. Our objective will be to minimize the maximum completion time of the jobs. We formulate the problem as a mixed integer program. Given this problem class is NP-hard in the strong sense, we present three lower bounds to estimate the optimal solution. We then propose a sequence-first, allocate-second heuristic approach for its solution. We heuristically decompose the problem by first creating a priority list to order the jobs and then assign the jobs to the available machines in each machine centre based on this order. We describe seven rules for the sequencing phase. The assignment phase consists of a heuristic which attempts to minimize each partial schedule length while looking ahead at the future assignment of the currently unscheduled jobs. The computational performance of the heuristic approach was evaluated by comparing the value of each heuristic variant to the best among the three lower bounds. Its effectiveness was tested on scenarios pertinent to flexible flowshop environments, such as cellular manufacturing, by conducting a computational study of over 3400 problems. Our computational results indicate that the most effective approach used Johnson's rule to provide the priority list for job assignment. This provided integrality gaps which on the average were less than 0·73%.     

Minimising makespan on a single batch processing machine with dynamic job arrivals and non-identical job sizes

Batch scheduling is a prevalent policy in many industries such as burn-in operations in semiconductor manufacturing and heat treatment operations in metalworking. In this paper, we consider the problem of minimising makespan on a single batch processing machine in the presence of dynamic job arrivals and non-identical job sizes. The problem under study is NP-hard. Consequently, we develop a number of efficient construction heuristics. The performance of the proposed heuristics is evaluated by comparing their results to two lower bounds, and other solution approaches published in the literature, namely the first-fit longest processing time-earliest release time (FFLPT-ERT) heuristic, hybrid genetic algorithm (HGA), joint genetic algorithm and dynamic programming (GA+DP) approach and ant colony optimisation (ACO) algorithm. The computational experiments demonstrate the superiority of the proposed heuristics with respect to solution quality, especially for the problems with small size jobs. Moreover, the computational costs of the proposed heuristics are very low.     

Applied column generation-based approach to solve supply chain scheduling problems

More and more enterprises have chosen to adopt a made-to-order business model in order to satisfy diverse and rapidly changing customer demand. In such a business model, enterprises are devoted to reducing inventory levels in order to upgrade the competitiveness of the products. However, reductions in inventory levels and short lead times force the operation between production and distribution to cooperate closely, thus increasing the practicability of integrating the production and distribution stages. The complexity of supply chain scheduling problems (integrated production and distribution scheduling) is known to be NP-hard. To address the issues above, an efficient algorithm to solve the supply chain scheduling problem is needed. This paper studies a supply chain scheduling problem in which the production stage is modelled by an identical parallel machine scheduling problem and the distribution stage is modelled by a capacitated vehicle routing problem. Given a set of customer orders (jobs), the problem is to find a supply chain schedule such that the weighted summation of total job weighted completion time and total job delivering cost are minimised. The studied problem was first formulated as an integer programme and then solved by using column generation techniques in conjunction with a branch-and-bound approach to optimality. The results of the computational experiments indicate that the proposed approach can solve the test problems to optimality. Moreover, the average gap between the optimal solutions and the lower bounds is no more than 1.32% for these test problems.     

Scheduling with controllable processing times and compression costs using population-based heuristics

This paper considers the single machine scheduling problem of jobs with controllable processing times and compression costs and the objective to minimise the total weighted job completion time plus the cost of compression. The problem is known to be intractable, and therefore it was decided to be tackled by population-based heuristics namely differential evolution (DE), particle swarm optimisation (PSO), genetic algorithms (GAs), and evolution strategies (ES). Population-based heuristics have found wide application in most areas of production research including scheduling theory. It is therefore surprising that this problem has not yet received any attention from the corresponding heuristic algorithms community. This work aims at contributing to fill this gap. An appropriate problem representation scheme is developed together with a multi-objective procedure to quantify the trade-off between the total weighted job completion time and the cost of compression. The four heuristics are evaluated and compared over a large set of test instances ranging from five to 200 jobs. The experiments showed that a differential evolution algorithm is superior (with regard to the quality of the solutions obtained) and faster (with regard to the speed of convergence) to the other approaches.     

Scheduling algorithms to minimise the total family flow time for job shops with job families

This paper considers the job scheduling problem in which jobs are grouped into job families, but they are processed individually. The decision variable is the sequence of the jobs assigned to each machine. This type of job shop scheduling can be found in various production systems, especially in remanufacturing systems with disassembly, reprocessing and reassembly shops. In other words, the reprocessing shop can be regarded as the job shop with job families since it performs the operations required to bring parts or sub-assemblies disassembled back to like-new condition before reassembling them. To minimise the deviations of the job completion times within each job family, we consider the objective of minimising the total family flow time. Here, the family flow time implies the maximum among the completion times of the jobs within a job family. To describe the problem clearly, a mixed integer programming model is suggested and then, due to the complexity of the problem, two types of heuristics are suggested. They are: (a) priority rule based heuristics; and (b) meta-heuristics. Computational experiments were performed on a number of test instances and the results show that some priority rule based heuristics are better than the existing ones. Also, the meta-heuristics improve the priority rule based heuristics significantly.