Experimental investigation of real-time scheduling in flexible manufacturing systems

This paper presents a new two-phase (TP) approximate method for real-time scheduling in a flexible manufacturing system (FMS). This method combines a reduced enumeration schedule generation algorithm with a 0–1 optimization algorithm. In order to make the combined algorithm practicable, heuristic rules are introduced for the selection of jobs to be scheduled. The relative performance of the TP method vis-a-vis conventional heuristic dispatching rules such as SPT, LPT, FCFS, MWKR, and LWKR is investigated using combined process-interaction/discrete-event simulation models. An efficient experimental procedure is designed and implemented using these models, and the statistical analysis of the results is presented. For the particular case investigated, the conclusions are very encouraging. In terms of mean flow time, the TP method performs significantly better than any other tested heuristic dispatching rules. Also, the experimental results show that using global information significantly improves the FMS performance.     

A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems

We consider the dynamic single-machine scheduling problem where the objective is to minimize the sum of weighted earliness and weighted tardiness costs. A single pass heuristic, based on decision theory, is developed for constructing schedules. The heuristic permits schedules with idle time between jobs and behaves like a dispatching procedure. The performance of the new heuristic is examined using 116 published problems for which the optimum solution is known. Its performance is also investigated using 540 randomly generated problems covering a variety of conditions by comparing it to two well known dispatching procedures, adapted for dynamic early/tardy problems. The results indicate that the heuristic performs very well.     

A heuristic for single machine scheduling with early and tardy costs

The problem of scheduling jobs with distinct ready times and due dates in a single machine to minimise the total earliness and tardiness penalties is considered. A constructive heuristic, which determines the sequence of jobs and simultaneously inserts idle times, is proposed. Adjacent pairwise interchange is then applied to the schedule obtained. For problems involving at most 12 jobs the heuristic solutions are compared to optimal solutions. For larger problems with up to 80 jobs the heuristic is tested against a local search based on pairwise interchanges and four dispatching rules presented in the literature. In each case, idle times are optimally inserted.     

Evolutionary search for difficult problem instances to support the design of job shop dispatching rules

Dispatching rules are simple scheduling heuristics that are widely applied in industrial practice. Their popularity can be attributed to their ability to flexibly react to shop floor disruptions that are prevalent in many real-world manufacturing environments. However, it is a challenging and time-consuming task to design local, decentralised dispatching rules that result in a good global performance of a complex shop.An evolutionary algorithm is developed to generate job shop problem instances for which an examined dispatching rule fails to achieve a good solution due to a single suboptimal decision. These instances can be easily analysed to reveal limitations of that rule which helps with the design of better rules. The method is applied to a job shop problem from the literature, resulting in new best dispatching rules for the mean flow time measure.     

Minimizing makespan with multiple-orders-per-job in a two-machine flowshop

We investigate a new scheduling problem, multiple-orders-per-job (MOJ), in the context of a two-machine flowshop. Lower bounds for the makespan performance measure are provided for combinations of lot-processing and item-processing machines. An optimization model is presented that addresses both job formation and job sequencing. We define a heuristic to minimize the makespan for the MOJ problem for two-machine item-processing flowshops. The heuristic obtains solutions within 2% of a tight lower bound and runs in O(HF) time, where H is the number of orders and F is the restricted number of jobs.     

A mixed integer programming model for scheduling orders in a steel mill

The problem of scheduling orders at each facility of a large integrated steel mill is considered. Orders are received randomly, and delivery dates are established immediately. Each order is filled by converting raw materials into a finished saleable steel product by a fixed sequence of processes. The application of a deterministic mixed integer linear programming model to the order scheduling problem is given. One important criterion permitted by the model is to process the orders in a sequence which minimizes the total tardiness from promised delivery for all orders; alternative criteria are also possible. Most practical constraints which arise in steelmaking can be considered within the formulation. In particular, sequencing and resource availability constraints are handled easily. The order scheduling model given here contains many variables and constraints, resulting in computational difficulties. A decomposition algorithm is devised for solving the model. The algorithm is a special case of Benders partitioning. Computational experience is reported for a large-scale problem involving scheduling 102 orders through ten facilities over a six-week period. The exact solution to the large-scale problem is compared with schedules determined by several heuristic dispatching rules. The dispatching rules took into consideration such things as due date, processing time, and tardiness penalties. None of the dispatching rules found the optimal solution.     

Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops

In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures.     

一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

针对延迟工件数最小的混合流水车间调度问题,给出了一种改进的模拟退火求解算法. 该算法首先给出一个启发式算法来获得初始解,然后用模拟退火算法对初始解改进. 通过交换工件在第一阶段的排序来获得一个新的解,采用最先空闲设备分配规则和先到先被加工规则,对工件在剩余各级的工序进行调度. 实验仿真表明算法是可行有效的.     

An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs

The problem of scheduling in a flowshop is considered with the objective of minimizing the total weighted flowtime of jobs. A heuristic algorithm is developed by the introduction of lower bounds on the completion times of jobs and the development of heuristic preference relations for the scheduling problem under study. An improvement scheme is incorporated in the heuristic to enhance the quality of its solution. The proposed heuristic, with and without the improvement scheme, and the existing heuristics are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that both versions of the proposed heuristic perform better than the existing heuristics in giving a superior solution quality and that the proposed heuristic without the improvement scheme yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the proposed heuristic and the existing heuristics, as well as the effectiveness of a variant of the scheme. The results are also discussed.     

Heuristic Performance and Network/Resource Characteristics in Resource-constrained Project Scheduling

The problem considered in this study is that of non-pre-emptive scheduling of the activities in a project network to minimize project duration under limited resource availabilities. Various heuristic rules and optimization techniques have been applied to this problem, and comparisons of their effectiveness have been made in the literature. However, no thorough investigation of the types of network and resource characteristics which play an underlying role in determining heuristic performance and which account for the variability of results has been made previously. In this study, a new heuristic rule which compares favourably with the widely-used heuristic rules is developed, and the influence of network/resource characteristics on the performance of different heuristic rules is investigated.     

Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags

This paper shows that the single machine scheduling problem with multiple operations per job separated by minimum specified time-lags is NP-hard in the strong sense. Seven simple and polynomially bounded heuristic algorithms are developed for its solution when each job requires only two operations. Empirical evaluation shows that the percentage deviation of the heuristic solutions from their lower bounds is quite low and the effectiveness of these heuristic algorithms in finding optimal schedules increases with an increase in the number of jobs.     

Minimizing flow time in a flow-line manufacturing cell with family setup times

This paper considers the problem of scheduling part families and jobs within each part family in a flowline manufacturing cell with independent family setup times where parts (jobs) in each family are processed together. The objective is to minimize total flow time. A branch-and-bound algorithm capable of solving moderate sized problems is developed. Several heuristic algorithms are proposed and empirically evaluated as to their effectiveness and efficiency in finding optimal permutation schedules. These results show that several heuristic algorithms generate solutions that are better than those generated by an existing genetic algorithm.     

New heuristics for total tardiness minimization in a flexible flowshop

This paper analyses the total tardiness minimization in a flowshop with multiple processors at each stage. While there is considerable research to minimize the makespan, very little work is reported on minimizing the total tardiness for this problem. This research focuses on heuristic methods that consider this environment as a series of parallel machine problems. New dispatching rules are introduced. One of the proposed rules is able to deal with jobs that will come afterwards and not only the available jobs at the decision time. Dispatching rules are also associated with classical (forward and backward) and new list scheduling algorithms. A special scheduling algorithm able to deal with idle times is proposed. Computational experiments in a set of 4,320 literature instances show that the developed heuristics are competitive and outperforms their classical counterparts.     

Job lateness in flowshops with setup and removal times separated

This paper addresses the two-machine flowshop problem where the setup, processing, and removal times of the jobs are separated and are independent of the job sequence. This problem is considered with maximum lateness as a measure of performance. Elimination criteria are established for both the classical and ordered flowshops, and optimal sequences are obtained for special ordered flowshops.     

A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times

This paper deals with hybrid flow-shop scheduling problem with rework. In this problem, jobs are inspected at the last stage, and poorly processed jobs were returned and processed again. Thus, a job may visit a stage more than once, and we have a hybrid flow-shop with re-entrant flow. This kind of a shop may occur in many industries, such as final inspection system in automotive manufacturing. The criterion is to minimize the makespan of the system. We developed a 0–1 mixed-integer program of the problem. Since the hybrid flow-shop scheduling problem is NP-hard, an algorithm for finding an optimal solution in polynomial time does not exist. So we generalized some heuristic methods based on several basic dispatching rules and proposed a variable neighbourhood search (VNS) for the problem with sequence-dependent set-up times and unrelated parallel machines. The computational experiments show that VNS provides better solutions than heuristic methods.     

Some no-wait shops scheduling problems: Complexity aspect

We investigate the computational complexity of no-wait shops scheduling problems. The problem of finding optimal finish time schedules is shown to be NP-hard for flowshops with two machine centres where each machine centre has one or more parallel machines for processing tasks. The complexity results are also reported for no-wait shops scheduling when all nonzero tasks have unit or identical processing time requirement. A polynomial time algorithm for 3-machine flowshops is proposed for optimal finish time schedules. Finding optimal finish time schedules in 2-machine jobshops in NP-hard. Also we establish NP-hard results for 3-machine jobshops for both optimal finish time and mean flow time schedules. Some results are deduced with the present work and with those reported earlier.     

Adaptive Control Model and Algorithms for the Dynamic Flowshop Scheduling Problem

1.IntroductionProductionschedulingcanbedefinedgenerallyastheallocationoftheresourcesinaproductionsystemovertimetoperformtheoperationsneededtotransformrawmaterialsilltoproducts.Aneffectiveandefficientschedulingsystemisnecessarytowellachievethepotentialsofaproductionfacility.Productionschedulingproblemsareextremelycomplex.Thecomplexityismainlyduetothefollowingtwofeaturesoftheproblem(Liu,1995).InterconnectedDecisions:Thecomponentsofaproductionsystem,e.g.,machines,ma-tenalhandlingdevicesandstora…     

Performance of the heuristic procedures for constrained projects with progress payments

All large scale resource constrained projects involve cash flows occurring during their life cycle. Several recent studies consider the problem of scheduling projects to maximise the net present value (NPV) of these cash flows. Their basic common assumption is that cash flows are mainly associated with specific events and they occur at event realisation times. An alternative assumption, which can be more realistic, is that cash inflows occur periodically, for example every month, as progress payments. This article considers the problem of maximising NPV given the alternative assumption. Three different heuristic rules are developed. The performance of these heuristic rules is analysed through a full factorial experiment with 108 scheduling conditions. The results indicate that three rules provide near-optimal schedules with respect to NPV maximisation while producing time schedules that do not delay the project completion time extensively.     

Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time

This paper considers the problems of scheduling jobs on parallel identical machines where an optimal schedule is defined as one that gives the smallest maximum tardiness (or the minimum number of tardy jobs) among the set of schedules with optimal total flow-time (the sum of the completion times of all jobs). We show that these problems are unary NP-Hard, develop lower bounds for these two secondary criteria problems, and describe heuristic algorithms for their solution. Results of a computational study show that the proposed heuristic algorithms are quite effective and efficient in solving these hierarchical criteria scheduling problems.     

A new dispatching rule based genetic algorithm for the multi-objective job shop problem

Hyper-heuristics or “methodologies to choose heuristics” are becoming increasingly popular given their suitability to solve hard real world combinatorial optimisation problems. Their distinguishing feature is that they operate in the space of heuristics or heuristic components rather than in the solution space. In Dispatching Rule Based Genetic Algorithms (DRGA) solutions are represented as sequences of dispatching rules which are called one at a time and used to sequence a number of operations onto machines. The number of operations that each dispatching rule in the sequence handles is a parameter to which DRGA is notoriously sensitive. This paper proposes a new hybrid DRGA which searches simultaneously for the best sequence of dispatching rules and the number of operations to be handled by each dispatching rule. The investigated DRGA uses the selection mechanism of NSGA-II when handling multi-objective problems.