Scheduling jobs on unrelated parallel machines to minimize regular total cost functions

In this paper we consider unrelated parallel machine scheduling problems that involve the minimization of regular total cost functions. We first present some properties of optimal solutions and then provide a lower bound. These mechanisms are tested on the well-known practical problem of minimizing total weighted flow time on unrelated parallel machines. In doing so, we design a branch and bound algorithm incorporating the mechanisms derived for the general total cost function along with the ones derived specifically for the total weighted flow time criterion. Computational experience indicates that incoiporating reduction and bounding mechanisms significantly improves the performance of the branch and bound algorithm.     

Open shop scheduling problem to minimize total weighted completion time

A given number of jobs in an open shop scheduling environment must each be processed for given amounts of time on each of a given set of machines in an arbitrary sequence. This study aims to achieve a schedule that minimizes total weighted completion time. Owing to the strong NP-hardness of the problem, the weighted shortest processing time block (WSPTB) heuristic is presented to obtain approximate solutions for large-scale problems. Performance analysis proves the asymptotic optimality of the WSPTB heuristic in the sense of probability limits. The largest weight block rule is provided to seek optimal schedules in polynomial time for a special case. A hybrid discrete differential evolution algorithm is designed to obtain high-quality solutions for moderate-scale problems. Simulation experiments demonstrate the effectiveness of the proposed algorithms.     

Collaborative reinforcement learning for a two-robot job transfer flow-shop scheduling problem

A two-robot flow-shop scheduling problem with n identical jobs and m machines is defined and evaluated for four robot collaboration levels corresponding to different levels of information sharing, learning and assessment: Full – robots work together, performing self and joint learning sharing full information; Pull – one robot decides when and if to learn from the other robot; Push – one robot may force the second to learn from it and None – each robot learns independently with no information sharing. Robots operate on parallel tracks, transporting jobs between successive machines, returning empty to a machine to move another job. The objective is to obtain a robot schedule that minimises makespan (C_max) for machines with varying processing times. A new reinforcement learning algorithm is developed, using dual Q-learning functions. A novel feature in the collaborative algorithm is the assignment of different reward functions to robots; minimising robot idle time and minimising job waiting time. Such delays increase makespan. Simulation analyses with fast, medium and slow speed robots indicated that Full collaboration with a fast–fast robot pair was best according to minimum average upper bound error. The new collaborative algorithm provides a tool for finding optimal and near-optimal solutions to difficult collaborative multi-robot scheduling problems.     

双机无等待流水作业调度算法研究

考虑双机无等待流水作业调度问题,此问题中每台机器都受一个非可用时间的约束,工件都有不同的释放时间。机器的非可用性时间间隔是部分重叠并且已知。目标使Makespan(最大流程时间)最小。通过不同的方式计算上限和下限,完善分支定界法。计算机实验结果显示了所述方法的有效性。     

Scheduling flexible flow lines with no in-process buffers

An heuristic algorithm is proposed for scheduling a flexible flow line with no intermediate buffers. The line is made up of several processing stages in series, where each stage has one or more identical parallel machines. In the line different part types can be manufactured simultaneously, each of which is processed by at most one machine in every stage. Intermediate queues of parts waiting between the stages for their next operations are not allowed. The problem objective is to minimize the makespan of the schedule for a set of part types selected for processing. The algorithm proposed is a part-by-part heuristic, in which during every iteration a complete processing schedule is determined for one part type selected for loading into the line. The selection of the part type and its complete schedule are based on the cumulative partial schedule obtained for all parts selected so far. The decisions in every iteration are made using a local optimization procedure aimed at minimizing total blocking and waiting time of the machines along the route of the selected part type. The efficiency of the algorithm is tested on several groups of random test problems     

Robust makespan minimisation in identical parallel machine scheduling problem with interval data

Parallel machine scheduling problems are commonly encountered in a wide variety of manufacturing environments and have been extensively studied. This paper addresses a makespan minimisation scheduling problem on identical parallel machines, in which the specific processing time of each job is uncertain, and its probability distribution is unknown because of limited information. In this case, the deterministic or stochastic scheduling model may be unsuitable. We propose a robust (min–max regret) scheduling model for identifying a robust schedule with minimal maximal deviation from the corresponding optimal schedule across all possible job-processing times (called scenarios). These scenarios are specified as closed intervals. To solve the robust scheduling problem, which is NP-hard, we first prove that a regret-maximising scenario for any schedule belongs to a finite set of extreme point scenarios. We then derive two exact algorithms to optimise this problem using a general iterative relaxation procedure. Moreover, a good initial solution (optimal schedule under a mid-point scenario) for the aforementioned algorithms is discussed. Several heuristics are developed to solve large-scale problems. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.     

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.     

Route-Dependent Open-Shop Scheduling

Open-shop scheduling, where the processing times of the operations constituting a job depend on the route by which it passes through the machines, is proved to be the master problem of which both open-shop and flow-shop scheduling are special cases. The two-machine, minimum-schedule-length case, where both open-shop and flow-shop scheduling problems belong to SP, is proved to be binary TISP-complete under a route-dependent open-shop discipline. An 0(n) algorithm is presented for a special case of the latter problem with a dominating machine.     

A meta-heuristic approach for solving the no-wait flow-shop problem

No-wait flow-shop scheduling problems refer to the set of problems in which a number of jobs are available for processing on a number of machines in a flow-shop context with the added constraint that there should be no waiting time between consecutive operations of the jobs. The problem is strongly NP-hard. In this paper, the considered performance measure is the makespan. In order to explore the feasible region of the problem, a hybrid algorithm of Tabu Search and Particle Swarm Optimisation (PSO) is proposed. In the proposed approach, PSO algorithm is used in order to move from one solution to a neighbourhood solution. We first employ a new coding and decoding technique to efficiently map the discrete feasible space to the set of integer numbers. The proposed PSO will further use this coding technique to explore the solution space and move from one solution to a neighbourhood solution. Afterwards, the algorithm decodes the solutions to its respective feasible solution in the discrete feasible space and returns the new solutions to the TS. The algorithm is tested by solving a large number of problems available in the literature. Computational results show that the proposed algorithm is able to outperform competitive methods and improves some of the best-known solutions of the considered test problems.     

Scheduling with alternatives: a link between process planning and scheduling

The objective of this research is to develop and evaluate effective, computationally efficient procedures for scheduling jobs in a large-scale manufacturing system involving, for example, over 1000 jobs and over 100 machines. The main performance measure is maximum lateness; and a useful lower bound on maximum lateness is derived from a relaxed scheduling problem in which preemption of jobs is based on the latest finish time of each job at each machine. To construct a production schedule that minimizes maximum lateness, an iterative simulation-based scheduling algorithm operates as follows: (a) job queuing times observed at each machine in the previous simulation iteration are used to compute a refined estimate of the effective due date (slack) for each job at each machine; and (b) in the current simulation iteration, jobs are dispatched at each machine in order of increasing slack. Iterations of the scheduling algorithm terminate when the lower bound on maximum lateness is achieved or the iteration limit is reached. This scheduling algorithm is implemented in Virtual Factory, a Windows-based software package. The performance of Virtual Factory is demonstrated in a suite of randomly generated test problems as well as in a large furniture manufacturing facility. To further reduce maximum lateness, a second scheduling algorithm also incorporates a tabu search procedure that identifies process plans with alternative operations and routings for jobs. This enhancement yields improved schedules that minimize manufacturing costs while satisfying job due dates. An extensive experimental performance evaluation indicates that in a broad range of industrial settings, the second scheduling algorithm can rapidly identify optimal or nearly optimal schedules.     

Sensitivity analysis of a fuzzy multiobjective scheduling problem

This paper concerns sensitivity analysis of a class of complex job shop scheduling problems which are characterized by: (1) a large number of jobs and machines, (2) uncertain jobs processing times, and (3) multiple measures of schedule performance including average weighted tardiness, the number of tardy jobs, the total setup times, the total idle time of machines, and the total flow times of jobs. The base schedule is generated by applying a new fuzzy multiobjective genetic algorithm which takes into consideration batching of the jobs of a similar type, jobs’ lots sizing and load balancing of the machines. The aim of the proposed sensitivity analysis of a generated schedule is to investigate the consequences of prolongations of job processing times on the measures of schedule performance. The processing times are described by triangular fuzzy numbers and their prolongation is done by expanding the supports of fuzzy numbers. The sensitivity analysis is performed through a series of numerical experiments. The effects of prolongations of job processing times on the measures of performance of a generated schedule are recorded and analysed. It is shown that the sensitivity analysis is among the primaries in evaluating the quality of a generated schedule. The sensitivity analysis is used in identifying the critical jobs and the critical machines which have the properties that the prolongations of their processing times produce the largest deteriorations of the performance measures and the overall quality of a generated schedule.     

Sequencing n Products Involving m Independent Jobs on m Machines

This article considers the problem of scheduling n products over m distinct machines. Every product consists of a set of jobs, each requiring a known processing time on a designated machine. There are no precedence constraints, and simultaneous processing of jobs requiring different machines within a product is allowed. The object of scheduling is to minimize a regular measure of performance associated with the products. It is shown that there exists an optimal schedule with the “no passing property.” Branch and bound routines are developed for finding the optimal solution for the two measures of performance: (1) total penalty cost; and (2) sum of product completion times. Comparisons between the optimal solution and solutions obtained using dispatching rules are given in the penalty cost case.     

Spread time considerations in operational fixed job scheduling

In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.     

Stability of Johnson's schedule with respect to limited machine availability

The paper deals with the scheduling problem of minimizing the makespan in the two -machine n -job flow-shop with w non-availability intervals on each of the two machines. This problem is binary NP-hard even if there is only one non-availability interval ( w = 1) either on the first machine or on the second machine. If there are no non-availability intervals on any machine ( w = 0), the two-machine flow-shop problem may be easily solved using Johnson's permutation of n jobs. We derived sufficient conditions for optimality of Johnson's permutation in the case of the given w S 1 non-availability intervals. The instrument we use is stability analysis, which answers the question of how stable an optimal schedule is if there are independent changes in the processing times of the jobs. The stability analysis is demonstrated on a huge number of randomly generated two -machine flow-shop problems with 5 h n h 10 000 and 1 h w h 1000.     

Flow-shop problems with intermediate buffers

In this paper the following extension of the classical flow-shop problem is considered: Between each two consecutive machines a buffer of limited capacity is given. After finishing processing on a machine, a job either directly has to be processed on the following machine or it has to be stored in the buffer between these machines. If the buffer is completely occupied the job may wait on its current machine but blocks this machine for other jobs. The objective is to determine a feasible schedule minimizing the makespan. To model such a problem setting, a variation of the classical disjunctive graph model for shop problems is extended. A tabu search procedure is described where neighborhoods based on an extension of the classical block approach theorem are used. Computational results for extended flow-shop benchmark instances are presented. Corespondence to: Silvia HeitmannThe authors are grateful to Tim Nieberg for implementing the tabu search procedure proposed in this paper.S. Heitmann     

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.     

A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness

This paper addresses a real-life production scheduling problem with identical parallel machines, originating from a plant producing Acrylonitrile-Butadiene-Styrene (ABS) plate products. In the considered practical scheduling problem, ABS plate has some specific specifications and each specification has several different levels. Because there is at least one different level of specification between two ABS plate products, it is necessary to make a set-up adjustment on each machine whenever a switch occurs from processing one ABS plate product to another product. As tardiness leads to extra penalty costs and opportunity losses, the objective of minimising total tardiness has become one of the most important tasks for the schedule manager in the plant. The problem can be classified as an identical parallel machine scheduling problem to minimise the total tardiness. A dispatching rule is proposed for this problem and evaluated by comparing it with the current scheduling method and several existing approaches. Moreover, an iterated greedy-based metaheuristic is developed to further improve the initial solution. The experimental results show that the proposed metaheuristic can perform better than an existing tabu search algorithm, and obtain the optimal solution for small-sized problems and significantly improve the initial solutions for large-sized problems.     

A hybrid GA/heuristic approach to the simultaneous scheduling of machines and automated guided vehicles

In this paper, the problem of simultaneous scheduling of machines and identical automated guided vehicles (AGVs) in flexible manufacturing systems is addressed with the objective of minimizing the makespan. This problem is composed of two interrelated decision problems: the scheduling of machines, and the scheduling of AGVs. Both problems are known to be NP-complete, resulting in a more complicated NP-complete problem when they are considered simultaneously. A new hybrid Genetic-algorithm/heuristic coding scheme is developed for the studied problem. The developed coding scheme is combined with a set of genetic algorithm (GA) operators selected from the literature of the applications of GAs to the scheduling problems. The algorithm is applied to a set of 82 test problems, which was constructed by other researchers, and the comparison of the results indicates the superior performance of the developed coding.     

Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times

This paper studies the makespan minimisation scheduling problem in a two-stage hybrid flow shop. The first stage has one machine and the second stage has m identical parallel machines. Neither the processing time nor probability distribution of the processing time of each job is uncertain. We propose a robust (min–max regret) scheduling model. To solve the robust scheduling problem, which is NP-hard, we first derive some properties of the worst-case scenario for a given schedule. We then propose both exact and heuristic algorithms to solve this problem. In addition, computational experiments are conducted to evaluate the performance of the proposed algorithms.     

A hybrid computer simulation-artificial neural network algorithm for optimisation of dispatching rule selection in stochastic job shop scheduling problems

Industrial systems are constantly subject to random events with inevitable uncertainties in production factors, especially in processing times. Due to this stochastic nature, selecting appropriate dispatching rules has become a major issue in practical problems. However, previous research implies that using one dispatching rule does not necessarily yield an optimal schedule. Therefore, a new algorithm is proposed based on computer simulation and artificial neural networks (ANNs) to select the optimal dispatching rule for each machine from a set of rules in order to minimise the makespan in stochastic job shop scheduling problems (SJSSPs). The algorithm contributes to the previous work on job shop scheduling in three significant ways: (1) to the best of our knowledge it is the first time that an approach based on computer simulation and ANNs is proposed to select dispatching rules; (2) non-identical dispatching rules are considered for machines under stochastic environment; and (3) the algorithm is capable of finding the optimal solution of SJSSPs since it evaluates all possible solutions. The performance of the proposed algorithm is compared with computer simulation methods by replicating comprehensive simulation experiments. Extensive computational results for job shops with five and six machines indicate the superiority of the new algorithm compared to previous studies in the literature.