Scheduling injection molding operations with multiple resource constraints and sequence dependent setup times and costs

This paper addresses a production scheduling problem in an injection molding facility. It appears to be the first attempt to schedule parallel machines for multiple items in presence of multiple capacitated resource constraints with sequence-dependent setup costs and times. The objective is to meet customer demands while minimizing the total inventory holding costs, backlogging costs and setup costs. We present a mathematical formulation of the problem. The computational complexity associated with the formulation makes it difficult for standard solvers address industrial-dimensioned problems in reasonable solution time. To overcome this, a two-phase workcenter-based decomposition scheme has been developed in this paper. The computational results for different problem sizes demonstrate that this scheme is able to solve industrial-dimensioned problems within reasonable time and accuracy.     

An optimal scheduling algorithm for an agent-based multicast strategy on irregular networks

This paper describes an agent-based approach for scheduling multiple multicast on wormhole switch-based networks with irregular topologies. Multicast/broadcast is an important communication pattern, with applications in collective communication operations such as barrier synchronization and global combining. Our approach assigns an agent to each subtree of switches such that the agents can exchange information efficiently and independently. The entire multicast problem is then recursively solved with each agent sending message to those switches that it is responsible for. In this way, communication is localized by the assignment of agents to subtrees. This idea can be easily generalized to multiple multicast since the order of message passing among agents can be interleaved for different multicasts. The key to the performance of this agent-based approach is the message-passing scheduling between agents and the destination processors. We propose an optimal scheduling algorithm, called ForwardInSwitch to solve this problem. We conduct extensive experiments to demonstrate the efficiency of our approach by comparing our results with SPCCO, a highly efficient multicast algorithm reported in literature. We found that SPCCO suffers link contention when the number of simultaneous multiple multicast becomes large. On the other hand, our agent-based approach achieves better performance in large cases.     

A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times

This paper addresses scheduling a set of jobs with specified release times on a single machine for delivery in batches to customers or to other machines for further processing. This problem is a natural extension of minimizing the sum of flow times in the presence of release time by considering the possibility of delivering jobs in batches and introducing batch delivery costs. The scheduling objective adopted is that of minimizing the sum of flow times and delivery costs. The extended problem arises in the context of coordination between machine scheduling and a distribution system in a supply chain network. Structural properties of the problem are investigated and used to devise a branch-and-bound solution scheme. Computational experiments show significant improvement over an existing dynamic programming algorithm.     

Dynamic scheduling of a batch of parallel task jobs on heterogeneous clusters

This paper addresses the problem of minimizing the scheduling length (make-span) of a batch of jobs with different arrival times. A job is described by a direct acyclic graph (DAG) of parallel tasks. The paper proposes a dynamic scheduling method that adapts the schedule when new jobs are submitted and that may change the processors assigned to a job during its execution. The scheduling method is divided into a scheduling strategy and a scheduling algorithm. We also propose an adaptation of the Heterogeneous Earliest-Finish-Time (HEFT) algorithm, called here P-HEFT, to handle parallel tasks in heterogeneous clusters with good efficiency without compromising the makespan. The results of a comparison of this algorithm with another DAG scheduler using a simulation of several machine configurations and job types shows that P-HEFT gives a shorter makespan for a single DAG but scores worse for multiple DAGs. Finally, the results of the dynamic scheduling of a batch of jobs using the proposed scheduler method showed significant improvements for more heavily loaded machines when compared to the alternative resource reservation approach.     

Minimizing maximum earliness on parallel identical machines

This paper addresses the scheduling problem of minimizing maximum earliness (or more generally — maximizing minimum lateness) on parallel identical machines. We prove that the two-machine case is NP-hard in the ordinary sense, and introduce a pseudo-polynomial dynamic programming algorithm for this case. When the number of machines is arbitrary, the problem is shown to be NP-hard in the strong sense. Then we introduce an efficient heuristic and two simple upper bounds on the optimal minimum lateness value. Finally we provide an extensive numerical study which indicates that the heuristic performs well in various job and machine settings.Scope and purposeIn recent years many researchers have focused on minimizing both earliness and tardiness costs. Only a few studies have considered problems with (maximum or total) earliness as the sole performance measure. We believe that the earliness measure is appropriate for many real-life settings, where the main cost component is the earliness (inventory) cost, and the tardiness (positive lateness) cost component is negligible. Our paper studies the scheduling problem of minmax earliness on parallel identical machines: we analyze the complexity of the problem, and introduce an efficient heuristic and simple bounds on the optimal cost.     

A hybrid scheduling approach for a two-stage flexible flow shop with batch processing machines

In this paper, we discuss a flexible flow shop scheduling problem with batch processing machines at each stage and with jobs that have unequal ready times. Scheduling problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). We are interested in minimizing the total weighted tardiness of the jobs. We present a mixed integer programming formulation. The batch scheduling problem is NP-hard. Therefore, an iterative stage-based decomposition approach is proposed that is hybridized with neighborhood search techniques. The decomposition scheme provides internal due dates and ready times for the jobs on the first and second stage, respectively. Each of the resulting parallel machine batch scheduling problems is solved by variable neighborhood search in each iteration. Based on the schedules of the subproblems, the internal due dates and ready times are updated. We present the results of designed computational experiments that also consider the number of machines assigned to each stage as a design factor. It turns out that the proposed hybrid approach outperforms an iterative decomposition scheme where a fairly simple heuristic based on time window decomposition and the apparent tardiness cost dispatching rule is used to solve the subproblems. Recommendations for the design of the two stages with respect to the number of parallel machines on each stage are given.     

Search heuristics for a parallel machine scheduling problem with ready times and due dates

We consider a problem of scheduling orders on identical parallel machines. An order can be released after a given ready time and must be completed before its due date. An order is split into multiple jobs (batches) and a job is processed on one of the parallel machines. The objective of the scheduling problem is to minimize the holding costs of orders including work-in-process as well as finished job inventories. We suggest two local search heuristics, simulated annealing and taboo search algorithms, for the problem. Performance of the suggested algorithms is tested through computational experiments on randomly generated test problems.     

A genetic algorithm approach to the multiple machine tool selection problem

A number of earlier researches have emphasized the on-the-job scheduling problems that occur with a single flexible machine. Two solutions to the problem have generally been considered; namely minimization of tool switches and minimization of tool switching instances. Methods used to solve the problems have included KTNS heuristic, dual-based relaxation heuristic, and non-LP-based branch-and-bound methods. However, scant literature has considered the case of job scheduling on multiple parallel machines which invokes another problem involving machine assignment. This paper addresses the problem of job scheduling and machine assignment on a flexible machining workstation (FMW) equipped with multiple parallel machines in a tool-sharing environment. Under these circumstances, the authors have attempted to model the problem with the objective of simultaneously minimizing both the number of tool switches and the number of tool switching instances. Furthermore, a set of realistic constraints has been included in the investigation. A novel genetic algorithm (GA) heuristic has been developed to solve the problem, and performance results show that GA is an appropriate solution.     

Approximation for scheduling on uniform nonsimultaneous parallel machines

We consider the problem of scheduling on uniform machines which may not start processing at the same time with the purpose of minimizing the maximum completion time. We propose using a variant of the MULTIFIT algorithm, LMULTIFIT, which generates schedules which end within 1.382 times the optimal maximum completion time for the general problem, and within \(\sqrt{6}/2\) times the optimal maximum completion time for problem instances with two machines. Both developments represent improvements over previous results. We prove that LMULTIFIT worst-case bounds for scheduling on simultaneous uniform machines are also LMULTIFIT worst-case approximation bounds for scheduling on nonsimultaneous uniform machines and show that worst-case approximation bounds of MULTIFIT variants for simultaneous uniform machines from previous literature also apply to LMULTIFIT. We also comment on how a PTAS for scheduling on a constant number of uniform machines with fixed jobs can be used to obtain a PTAS for scheduling on a constant number of uniform nonsimultaneous parallel machines.     

Integrating the lot-sizing and sequencing decisions for scheduling a capacitated flow line

In this paper we consider a general problem of scheduling a single flow line consisting of multiple machines and producing a given set of jobs. The manufacturing environment is characterized by sequence dependent set-up times, limited intermediate buffer space, and capacity constraints. In addition, jobs are assigned with due dates that have to be met. The objectives of the scheduling are: (1) to meet the due dates without violating the capacity constraints, (2) to minimize the makespan, and (3) to minimize the inventory holding costs. While most of the approaches in the literature treat the problem of scheduling in flow lines as two independent sub-problems of lot-sizing and sequencing, our approach integrates the lot-sizing and sequencing heuristics. The integrated approach uses the Silver-Meal heuristic (modified to include lot-splitting) for lot-sizing and an improvement procedure applied to Palmer's heuristic for sequencing, which takes into account the actual sequence dependent set-up times and the limited intermedite buffer capacity. We evaluate the performance of the integrated approach and demonstrate its efficacy for scheduling a real world SMT manufacturing environment.     

Dynamic scheduling using a pheromone-based approach in multi-agent systems

The scheduling problems in factory domain applications usually involve many parallel machines, with each machine capable of processing several tasks. In most cases, changing the current machine state to another state to process a different task incurs additional material costs and time. If the overall system can maintain the expected performance, minimizing these state changes is very beneficial, and agent-based approaches inspired by the task allocation strategies of several social insects have gained increasing attention as solutions. The basic concept is based on the stimulus-threshold relation, and an individual agent determines whether it performs a given task or not based on two sets of terms, the environmental external stimuli for the task and the internal threshold values of all possible tasks. In this approach, selecting appropriate threshold values is directly related to the overall system performance, and we present a pheromone-based approach to obtain appropriate threshold values. Each agent maintains a limited, constant-sized task history queue of recently processed tasks, and the information of each agent is individually used to calculate the threshold values of tasks. Based on various experimental results, we show that the performance of the proposed method is comparable to those of other conventional methods.     

Power and performance management for parallel computations in clouds and data centers

We address scheduling independent and precedence constrained parallel tasks on multiple homogeneous processors in a data center with dynamically variable voltage and speed as combinatorial optimization problems. We consider the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing energy consumption with schedule length constraint on multiple processors. Our approach is to use level-by-level scheduling algorithms to deal with precedence constraints. We use a simple system partitioning and processor allocation scheme, which always schedules as many parallel tasks as possible for simultaneous execution. We use two heuristic algorithms for scheduling independent parallel tasks in the same level, i.e., SIMPLE and GREEDY. We adopt a two-level energy/time/power allocation scheme, namely, optimal energy/time allocation among levels of tasks and equal power supply to tasks in the same level. Our approach results in significant performance improvement compared with previous algorithms in scheduling independent and precedence constrained parallel tasks.     

Two Machine Scheduling under Disruptions with Transportation Considerations

Effective logistics scheduling requires synchronization of manufacturing and delivery to optimize customer service at minimum total cost. In this paper, we study a new scheduling problem that arises in a disruption environment. Such a problem occurs when a disruption unexpectedly happens, and consequently, some machines become unavailable for certain periods. Jobs that are assigned to the disrupted machines and have not yet been processed can either be moved to other available machines for processing, which may involve additional transportation time and cost, or can be processed by the same machine after the disruption. Our goal is to reschedule jobs so that an objective function, including the original cost function, and possibly transportation costs and disruption cost caused by deviating from the originally planned completion times, is minimized. In this paper, we focus on the two-machine case to demonstrate some major properties, and hope that these properties can provide insights for solving other general problems, such as multiple (more than two) machine scheduling and machine scheduling in other configurations (job shop or flow shop) under disruption. We study problems with different related costs. In each problem, we either provide a polynomial algorithm to solve the problem optimally, or show its NP-hardness. If the problem is NP-hard in the ordinary sense, we also present a pseudo-polynomial algorithm to solve the problem optimally. This research is supported in part by Hong Kong RGC grant HKUST 6145/03E and in part by NSF Grant DMI-0300156.     

A Constructive Genetic Algorithm for permutation flowshop scheduling

The general flowshop scheduling problem is a production problem where a set of n jobs have to be processed with identical flow pattern on m machines. In permutation flowshops the sequence of jobs is the same on all machines. A significant research effort has been devoted for sequencing jobs in a flowshop minimizing the makespan. This paper describes the application of a Constructive Genetic Algorithm (CGA) to makespan minimization on flowshop scheduling. The CGA was proposed recently as an alternative to traditional GA approaches, particularly, for evaluating schemata directly. The population initially formed only by schemata, evolves controlled by recombination to a population of well-adapted structures (schemata instantiation). The CGA implemented is based on the NEH classic heuristic and a local search heuristic used to define the fitness functions. The parameters of the CGA are calibrated using a Design of Experiments (DOE) approach. The computational results are compared against some other successful algorithms from the literature on Taillard’s well-known standard benchmark. The computational experience shows that this innovative CGA approach provides competitive results for flowshop scheduling problems.     

Scheduling and Lot Streaming in Flowshops with No-Wait in Process

Lot streaming involves splitting a production lot into a number of sublots, in order to allow the overlapping of successive operations, in multi-machine manufacturing systems. In no-wait flowshop scheduling, sublots are necessarily consistent, that is, they remain the same over all machines. The benefits of lot streaming include reductions in lead times and work-in-process, and increases in machine utilization rates. We study the problem of minimizing the makespan in no-wait flowshops producing multiple products with attached setup times, using lot streaming. Our study of the single product problem resolves an open question from the lot streaming literature. The intractable multiple product problem requires finding the optimal number of sublots, sublot sizes, and a product sequence for each machine. We develop a dynamic programming algorithm to generate all the nondominated schedule profiles for each product that are required to formulate the flowshop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and computationally test an efficient heuristic for this problem. Our results indicate that solutions can quickly be found for flowshops with up to 10 machines and 50 products. Moreover, the solutions found by our heuristic provide a substantial improvement over previously published results.     

Optimization of parts scheduling in multiple cells considering intercell move using scatter search approach

This paper addresses the problem of parts scheduling in a cellular manufacturing system (CMS) by considering exceptional parts processed on machines located in multiple cells. To optimize the scheduling of parts as well as to minimize material handling between cells, the practice has to develop processing sequences for the parts in cells. A commonly chosen objective is to find part sequences within cells which results in a minimum tardiness. This paper proposes a nonlinear mathematical programming model of the problem by minimizing the total weighted tardiness in a CMS. To solve the mathematical model, a scatter search approach is developed, in which the common components of scatter search are redefined and redesigned so as to better fit the problem. This scatter search approach considers two different methods to generate diverse initial solutions and two improvement methods, and adopts the roulette wheel selection in the combination method to further expand the conceptual framework and implementation of the scatter search. The proposed approach is compared with the commercial solver CPLEX on a set of test problems, some of which are large dimensions. Computational results have demonstrated the effectiveness of this scatter search approach.     

Identifying FMS repetitive patterns for efficient search-based scheduling algorithm: A colored Petri net approach

The multiple lot size scheduling problem plays a crucial role in minimizing production and setup costs in order to respond to constant fluctuations in customer demands. However, the computational cost to optimize a scheduling problem increases as the lot size of jobs increases, leading to a scalability problem for most scheduling algorithms. This paper presents an efficient search approach based on colored Petri net (CPN) formalism that addresses the state explosion problem of reachability graphs used for finding the optimal solutions to scheduling problems. To reduce the memory requirements, the proposed approach exploits the structural equivalence found in the reachability graphs of flexible manufacturing systems’ (FMS) CPNs to discard states once they are no longer needed to explore the state space. The hypothetical structural equivalence is attributed to the repetitive patterns identified in the execution of manufacturing processes when the lot sizes of jobs are scaled for FMS whose underlying layout configuration is fixed. We present the concept of structural equivalence based on duplicate state detection for FMS of different lot sizes and give sufficient conditions under which the structural equivalence obtained from a few lot size (smaller) instances holds for the same FMS of a larger size. The approach is validated experimentally on different FMS examples which confirm that the behavior of an FMS of any large lot size can be inferred from the FMS of a smaller size. Experimental results indicate that this work performs better than prior search methods and obtains optimal schedules of FMS with large lot sizes. Also, we show that the approach is applicable to FMS problems of similar configurations where the problem size differ by the number of jobs, resources and operations.     

Preemptive Scheduling on Uniform Parallel Machines with Controllable Job Processing Times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.     

Integrated process planning and scheduling by an agent-based ant colony optimization

This paper presents an ant colony optimization (ACO) algorithm in an agent-based system to integrate process planning and shopfloor scheduling (IPPS). The search-based algorithm which aims to obtain optimal solutions by an autocatalytic process is incorporated into an established multi-agent system (MAS) platform, with advantages of flexible system architectures and responsive fault tolerance. Artificial ants are implemented as software agents. A graph-based solution method is proposed with the objective of minimizing makespan. Simulation studies have been established to evaluate the performance of the ant approach. The experimental results indicate that the ACO algorithm can effectively solve the IPPS problems and the agent-based implementation can provide a distributive computation of the algorithm.     

A novel artificial immune system for solving multiobjective scheduling problems subject to special process constraint

This study presents a novel artificial immune system for solving a multiobjective scheduling problem on parallel machines (MOSP), which has the following characteristics: (1) parallel machines are nonidentical, (2) the type of jobs processed on each machine can be restricted, and (3) the multiobjective scheduling problem includes minimizing the maximum completion time among all the machines (makespan) and minimizing the total earliness/tardiness penalty of all the jobs. In this proposed algorithm, the cells are represented by a vector group, and a local search algorithm is incorporated to facilitate the exploitation of the search space. Specially, a new diversity technique is proposed to preserve the diversity of the population and enhance the exploration of the solution space. Simulation results show the proposed algorithm outperforms the vector immune genetic algorithm (VIGA).