Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics

We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be calculated efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to effectively reduce the size of the MIP formulation. In order to handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job of the earliest due date to a machine with least recipe changeover (EDDLC) and try to re-optimize the solution by local search heuristics which involves interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually gives solutions very close to the exact optimum for smaller scheduling problems, and calculates good solutions for scheduling up to 200 jobs on 40 machines within 10 min.     

A Genetic Algorithm Approach to the Scheduling of FMSs with Multiple Routes

Usually, most of the typical job shop scheduling approaches deal with the processing sequence of parts in a fixed routing condition. In this paper, we suggest a genetic algorithm (GA) to solve the job-sequencing problem for a production shop that is characterized by flexible routing and flexible machines. This means that all parts, of all part types, can be processed through alternative routings. Also, there can be several machines for each machine type. To solve these general scheduling problems, a genetic algorithm approach is proposed and the concepts of virtual and real operations are introduced. Chromosome coding and genetic operators of GAs are defined during the problem solving. A minimum weighted tardiness objective function is used to define code fitness, which is used for selecting species and producing a new generation of codes. Finally, several experimental results are given.     

Analysis of reactive deadlock-free scheduling in flexible job shops

Reactive scheduling is a procedure followed in production systems to react to unforeseen events that disturb the normal operation of the system. In this paper, a novel operations insertion heuristic is proposed to solve the deadlock-free reactive scheduling problem in flexible job shops, upon the arrival of new jobs. The heuristic utilizes rank matrices (Latin rectangles) to insert new jobs in schedules, while preventing the occurrence of deadlocks or resolving them using the available buffer space (if any). Jobs with alternative processing routes through the system are also considered. The heuristic can be employed to execute two reactive scheduling approaches in a timely efficient manner; to insert the new jobs in the already existing schedule (job insertion) or to reschedule all the jobs in the system (total rescheduling). Using experimental design and analysis of variance (ANOVA), the relative performance of the two approaches is studied and analyzed to provide some measures and guidelines for selecting the appropriate reactive scheduling approach for different problem settings. Three measures of performance are considered in the analysis; efficiency of the revised schedules in terms of the mean flow time, resulting system nervousness, and the required solution time. The results show that, on average, job insertion obtains revised schedules featuring significantly lower system nervousness and slightly higher mean flow time than total rescheduling. However, depending on the system size, number and processing times of the new jobs, and the available flexibility in the system, a trade-off between the two approaches should sometimes be considered.     

Service control with the preemptive parallel job scheduler Scojo-PECT

User satisfaction and scheduling on grids makes predictability of response times and quality-of-service highly desirable. However, existing approaches for response-time prediction still show significant prediction errors, mostly due to problems in dynamic arrival of jobs with potentially higher priority and hard-to-anticipate packing and backfilling effects. The same problems imply that quality-of-service cannot be solved with standard approaches from communication systems. Thus, this paper presents a scheduling approach which provides a more suitable framework for service guarantees and predictability. The approach is based on coarse-grain preemption, combined with an innovative separation of job classes. Resource shares can be determined as necessary to meet target service levels. A further extension permits limited dynamic resource allocation to adapt to variations in machine load and job mixes. The feasibility of service control is demonstrated with various workloads.     

A framework for capacity planning and machine configuration in flexible assembly systems

We consider the problem of simultaneously determining the number of machines (and/or workers), the assignment of tasks (and related tools and components) to these machines, and the number of jobs circulating in a flexible assembly system (FAS), to satisfy steady-state throughput requirements for a family of similar products at minimum cost. We focus on situations where there are precedence relations among the various tasks, as is common in assembly systems. We present a framework for solving this problem based on a heuristic decomposition approach which involves the solution of only a few types of sub-problems. We demonstrate the efficiency and effectiveness of the overall procedure using a number of example problems.     

Job scheduling and management of wearing tools with stochastic tool lifetimes

The problem of scheduling jobs using wearing tools is studied. Tool wearing is assumed to be stochastic and the jobs are processed in one machining centre provided with a limited capacity tool magazine. The aim is to minimize the expected average completion time of the jobs by choosing their processing order and tool management decisions wisely. All jobs are available at the beginning of the planning period. This kind of situation is met in production planning of CNC-machines. Previous studies concerning this problem have either assumed deterministic wearing for the tools or omitted the wearing completely. In our formulation of the problem, tool wearing is stochastic and the problem becomes very hard to solve analytically. A heuristic based on genetic algorithms is therefore given for the joint problem of job scheduling and tool management. The algorithm searches the most beneficial job sequence when the tool management decisions are made by a removal rule taking into account the future planned usage of the tools. The cost of each job sequence is evaluated by simulating the job processing. Empirical tests with heuristics indicate that by taking the stochastic information into account, one can reduce the average job processing time considerably.     

Decomposition methods for scheduling semiconductor testing facilities

We present decomposition procedures for scheduling semiconductor testing facilities. These facilities are characterized by the presence of different types of work centers, some of which have sequence-dependent setup times and some parallel identical machines. We exploit the structure of the routings in semiconductor testing to develop tailored decomposition procedures that decompose the shop into a number of work centers that are scheduled using specialized procedures. Extensive computational experiments show that these procedures significantly outperform existing methods in reasonable CPU times. These results indicate that decomposition methods can be successfully applied to complex scheduling problems of the type addressed in this paper, as well as the classical job shop problems addressed in previous research.     

A flexible crane scheduling methodology for container terminals

In this paper, we propose a flexible neighbourhood search strategy for quay crane scheduling problems based on the framework of tabu search (TS) algorithm. In the literature, the container workload of a ship is partitioned into a number of fixed jobs to deal with the complexity of the problem. In this paper, we propose flexible jobs which are dynamically changed by TS throughout the search process to eliminate the impact of fixed jobs on the generated schedules. Alternative job sequences are investigated for quay cranes and a new quay crane dispatching policy is developed to generate schedules. Computational experiments conducted with problem instances available in the literature showed that our algorithm is capable of generating quality schedules for quay crane handling operations at reasonable times.     

Task scheduling for MapReduce in heterogeneous networks

In this paper, the task scheduling in MapReduce is considered for geo-distributed data centers on heterogeneous networks. Adaptive heartbeats, job deadlines and data locality are concerned. Job deadlines are divided according to the maximum data volume of tasks. With the considered constraints, the task scheduling is formulated as an assignment problem in each heartbeat, in which adaptive heartbeats are calculated by the processing times of tasks, jobs are sequencing in terms of the divided deadlines and tasks are scheduled by the Hungarian algorithm. Taking into account both the data transfer and processing times, the most suitable data center for all mapped jobs are determined in the reduce phase. Experimental results show that the proposed algorithms outperform the current existing ones. The proposals with sorted task-sequences have better performance than those with random task-sequences.     

Steady-State Analysis and Scheduling of Cyclic Job Shops with Overtaking

A cyclic shop is a production system that repeatedly produces identical sets of parts of multiple types, called minimal part sets (MPSs), in the same loading and processing sequence. A different part type may have a different machine visit sequence. We consider a version of cyclic job shop where some operations of an MPS instance are processed prior to some operations of the previous MPS instances. We call such a shop an overtaking cyclic job shop (OCJS). The overtaking degree can be specified by how many MPS instances the operations of an MPS instance can overtake. More overtaking results in more work-in-progress, but reduces the cycle time, in general. We prove that for a given processing sequence of the operations at each machine, under some conditions, an OCJS has a stable earliest starting schedule such that each operation starts as soon as its preceding operations are completed, the schedule repeats an identical timing pattern for each MPS instance, and the cycle time is kept to be minimal. To do these, we propose a specialized approach to analyzing steady states for an event graph model of an OCJS that has a cyclic structure, which can keep the MPS-based scheduling concept. Based on the steady-state results, we develop a mixed integer programming model for finding a processing sequence of the operations at each machine and the overtaking degrees, if necessary, that minimize the cycle time.     

Multiple-Objective Scheduling for the Hierarchical Control of Flexible Manufacturing Systems

This paper presents a hierarchical approach to scheduling flexible manufacturing systems (FMSs) that pursues multiple performance objectives and considers the process flexibility of incorporating alternative process plans and resources for the required operations. The scheduling problem is solved at two levels: the shop level and the manufacturing system level. The shop level controller employs a combined priority index developed in this research to rank shop production orders in meeting multiple scheduling objectives. To overcome dimensional complexity and keep a low level of work-in-process inventory, the shop controller first selects up to three production orders with the highest ranking as candidates and generates all possible release sequences for them, with or without multitasking. These sequences are conveyed to the manufacturing system controller, who then performs detailed scheduling of the machines in the FMS using a fixed priority heuristic for routing parts of multiple types while considering alternative process plans and resources for the operations. The FMS controller provides feedback to the shop controller with a set of suggested detailed schedules and projected order completion times. On receiving these results, the shop controller further evaluates each candidate schedule using a multiple-objective function and selects the best schedule for execution. This allows multiple performance objectives of an FMS to be achieved by the integrated hierarchical scheduling approach.     

Component Partitioning Under Demand and Capacity Uncertainty in Printed Circuit Board Assembly

This paper considers the problem of configuring a printed circuit board (PCB) assembly line experiencing uncertainty in demand and capacity. The PCB assembly process involves a single line of automatic placement machines, a variety of board types, and a number of component types. The line is set up only once, at the beginning of a production cycle, to eliminate setups between board types. Using this strategy, the line therefore can assemble all different types of PCBs without feeder changes. The problem then becomes to partition component types to the different machines in the hope of processing all boards quickly with a good workload balance. In this paper, the board demands and machine breakdowns are random but follow some probability distribution, which can be predicted from past observations of the system. We formulate this problem as a stochastic mixed-integer programming formulation with the objective of minimizing the expected makespan for assembling all PCBs during a production cycle. The results obtained indicate significant improvement over the existing methods. We hope that this research will provide more PCB assembly facilities with models and techniques to hedge against variable forecasts and capacity plans     

Optimal dispatching of multipriority jobs to two heterogeneous workstations

The general problem scenario of this paper is the following: Jobs of various priorities, stationed in a common storage area, are waiting to be dispatched to two non-identical workstations. Any of the waiting jobs can be accessed from the storage at any given time. Each job can be processed on either of the workstations, but once a job has been assigned it may not be preempted. By job priority it is meant that a higher priority job has disptach preference over a lower priority job. The processing time of a job on a given workstation is assumed to be random, the distribution being dependent on the job type and the configuration of the workstation. Specifically, the first problem studied considers only two classes of jobs: (1) “hot” jobs, whose processing is to be expedited and thus have the higher dispatch priority, and (2) “routine” jobs which may be assigned to an available workstation only if the workstation has been rejected by all “hot” jobs. The processing times are assumed to be exponentially distributed with means depending on the job class and workstation. We assume that, on the average, one workstation is faster than the other with regard to processing any job. The dispatching objective for each job class is to minimize its expected flowtime. It is shown that threshold dispatching policies are optimal for this problem. That is, the faster processor should be utilized whenever possible, and for each class there exists an explicit threshold such that when the number of jobs of that class in the buffer exceeds this threshold then a job of that class is dispatched to the slower processor, otherwise these jobs wait for the faster processor to become available. For the higher priority jobs, this threshold is shown to be a function only of the various processing rates of the two workstations. For the lower priority jobs, the threshold also depends on the number of higher priority jobs in the buffer. The results is extended to a system with n priority classes. Again, it is shown that when the processing times are exponentially distributed with different rates and the dispatching objective for each class is to minimize its expected flowtime, the optimal dispatching policies are of threshold type. Explicit thresholds are easily derived.     

Planning the routing mix in FASs to minimize total transportation time

The routing mix problem in flexible assembly systems is considered. The problem consists of assigning the operations for each part to the machines, with the two objectives of balancing the machine workloads and minimizing the burden of the transportation system. These two objectives are sometimes conflicting, since the latter tends to support assigning operations to the same machine(s) as much as possible, and this may be bad for workload balancing. A linear programming problem is presented that, given a constraint on the workload of each machine, finds one solution that minimizes the overall time spent moving the parts from one machine to another. Since such a linear program may have an exponential number of variables, an efficient column generation technique to solve the problem is devised. The efficiency of the method is validated by experiments on a large number of random problems.     

More reliable protein NMR peak assignment via improved 2-interval scheduling.

Protein NMR peak assignment refers to the process of assigning a group of "spin systems" obtained experimentally to a protein sequence of amino acids. The automation of this process is still an unsolved and challenging problem in NMR protein structure determination. Recently, protein NMR peak assignment has been formulated as an interval scheduling problem (ISP), where a protein sequence P of amino acids is viewed as a discrete time interval I (the amino acids on P one-to-one correspond to the time units of I), each subset S of spin systems that are known to originate from consecutive amino acids from P is viewed as a "job" j(s), the preference of assigning S to a subsequence P of consecutive amino acids on P is viewed as the profit of executing job j(s) in the subinterval of I corresponding to P, and the goal is to maximize the total profit of executing the jobs (on a single machine) during I. The interval scheduling problem is max SNP-hard in general; but in the real practice of protein NMR peak assignment, each job j(s) usually requires at most 10 consecutive time units, and typically the jobs that require one or two consecutive time units are the most difficult to assign/schedule. In order to solve these most difficult assignments, we present an efficient 13/7-approximation algorithm for the special case of the interval scheduling problem where each job takes one or two consecutive time units. Combining this algorithm with a greedy filtering strategy for handling long jobs (i.e., jobs that need more than two consecutive time units), we obtain a new efficient heuristic for protein NMR peak assignment. Our experimental study shows that the new heuristic produces the best peak assignment in most of the cases, compared with the NMR peak assignment algorithms in the recent literature. The above algorithm is also the first approximation algorithm for a nontrivial case of the well-known interval scheduling problem that breaks the ratio 2 barrier.     

Two game-based solution concepts for a two-agent scheduling problem

In the current research papers on multi-agent (multi-person) scheduling, a person’s objective function is always considered as a cost function on scheduling, whereas a cooperative profit function is defined to serve as his objective one in this paper. In the two-person scheduling problem addressed in this paper, the two persons jointly order a common operational time interval of a single machine. Each person needs to process a set of his own jobs in that time window. The same objective function of each person still relies on the sequence of all the jobs of both persons since each part of the function is determined by some given parameters except one part assumed to be a given multiple of the total completion time of his own jobs. The two persons have to negotiate a job sequence and determine the (related) final solution on cooperative profit allocation. Such a two-person scheduling problem is essentially a cooperative game. An algorithm is designed to yield the cooperative-profit-based Pareto efficient solution set acting as the first game-based solution concept in this paper. The parallelized version of the algorithm is also developed. The second game-based solution concept is the Shapley value appropriate for the above cooperative-game situation on two-person scheduling. Several instances are presented and analyzed to reveal the necessity to employ the two solution concepts together.     

The Effects of Scheduling Rules and Routing Flexibility on the Performance of a Random Flexible Manufacturing System

The increased use of flexible manufacturing systems to efficiently provide customers with diversified products has created a significant set of operational challenges for managers. Many issues concerning procedures and policies for the day-to-day operation of these systems still are unresolved. Previous studies in this area have concentrated on various problems by isolating or simplifying the systems under study. The primary objective of this study is to extend previous research by examining the effects of scheduling rules and routing flexibility on the performance of a constrained, random flexible manufacturing system (FMS). Other experimental factors considered are shop load, shop configuration, and system breakdowns. Within the bounds of this experiment, the results indicate that, in the presence of total routing flexibility, the effects of shop load, system breakdowns, and scheduling rules are significantly dampened. In particular, when total routing flexibility exists, the choice of scheduling rules is not critical. We also show that the behavior of scheduling rules in a more constrained FMS environment (i.e., where system breakdowns occur and material handling capability is limited) is consistent with the findings of previous research conducted under less constrained environments. Finally, results indicate that the shop configuration factor has little or no impact on a system's flow-time performance.     

An iterative approach to system setup problems in flexible manufacturing systems

System setup problems in flexible manufacturing systems deal with short-term planning problems such as part type selection, machine grouping, operation assignment, tooling, fixture and pallet allocation, and routing. In this article, we consider three of the subproblems: part type selection, machine grouping, and loading. We suggest a heuristic approach to solve the subproblems consistently with the objective of maximizing the expected production rate. The proposed procedure includes routines to generate all possible machine grouping alternatives for a given set of machines, to obtain optimal target workloads for each grouping alternative, and to allocate operations and tools to machine groups. These routines are executed iteratively until a good solution to the system setup problem is obtained. Computational experience is reported.     

Cost-aware job scheduling for cloud instances using deep reinforcement learning

As the services provided by cloud vendors are providing better performance, achieving auto-scaling, load-balancing, and optimized performance along with low infrastructure maintenance, more and more companies migrate their services to the cloud. Since the cloud workload is dynamic and complex, scheduling the jobs submitted by users in an effective way is proving to be a challenging task. Although a lot of advanced job scheduling approaches have been proposed in the past years, almost all of them are designed to handle batch jobs rather than real-time workloads, such as that user requests are submitted at any time with any amount of numbers. In this work, we have proposed a Deep Reinforcement Learning (DRL) based job scheduler that dispatches the jobs in real time to tackle this problem. Specifically, we focus on scheduling user requests in such a way as to provide the quality of service (QoS) to the end-user along with a significant reduction of the cost spent on the execution of jobs on the virtual instances. We have implemented our method by Deep Q-learning Network (DQN) model, and our experimental results demonstrate that our approach can significantly outperform the commonly used real-time scheduling algorithms.

     

Genetic Algorithm Based Scheduling of Meta-Tasks with Stochastic Execution Times in Heterogeneous Computing Systemst1

In this study, we address the meta-task scheduling problem in heterogeneous computing (HC) systems, which is to find a task assignment that minimizes the schedule length of a meta-task composed of several independent tasks with no data dependencies. The fact that the meta-task scheduling problem in HC systems is NP-hard has motivated the development of many heuristic scheduling algorithms. These heuristic algorithms, however, neglect the stochastic nature of task execution times in an attempt to minimize a deterministic objective function, which is the maximum of the expected values of machine loads. Contrary to existing heuristics, we account for this stochastic nature by modeling task execution times as random variables. We, then, formulate a stochastic scheduling problem where the objective is to minimize the expected value of the maximum of machine loads. We prove that this new objective is underestimated by the deterministic objective function and that an optimal task assignment obtained with respect to the deterministic objective function could be inefficient in a real computing platform. In order to solve the stochastic scheduling problem posed, we develop a genetic algorithm based scheduling heuristic. Our extensive simulation studies show that the proposed genetic algorithm can produce better task assignments as compared to existing heuristics. Specifically, we observe a performance improvement on the relative cost heuristic (M.-Y. Wu and W. Shu, A high-performance mapping algorithm for heterogeneous computing systems, in: Int. Parallel and Distributed Processing Symposium, San Francisco, CA, April 2001) by up to 61%.