Search

This paper presents an iterated local search (ILS) algorithm for the single machine total weighted tardiness batch scheduling problem. To our knowledge, this is one of the first attempts to apply ILS to solve a batching scheduling problem. The proposed algorithm contains a local search procedure that explores five neighborhood structures, and we show how to efficiently implement them. Moreover, we compare the performance of our algorithm with dynamic programming-based implementations for the problem, including one from the literature and two other ones inspired in biased random-key genetic algorithms and ILS. We also demonstrate that finding the optimal batching for the problem given a fixed sequence of jobs is NP -hard, and provide an exact pseudo-polynomial time dynamic programming algorithm for solving such problem. Extensive computational experiments were conducted on newly proposed benchmark instances, and the results indicate that our algorithm yields highly competitive results when compared to other strategies. Finally, it was also observed that the methods that rely on dynamic programming tend to be time-consuming, even for small size instances. [ABSTRACT FROM AUTHOR]

An S-stage hybrid (or flexible) flow shop, with sequence-independent uniform set-up times, parallel batching machines with compatible parallel batch families (like in casting or heat treatments in furnaces, chemical or galvanic baths, painting in autoclave, etc.) has been analysed with the purpose of reducing the number of tardy jobs (and the makespan); in Graham's notation: FPB(m1, m2, ..., mS)|p-batch,. Jobs are sorted dynamically (at each new delivery); batches are closed within sliding (or rolling) time windows and processed in parallel by multiple identical machines. Computation experiments have shown the better performance on benchmarks of the two proposed heuristics based on new formulations of the critical ratio (CRsetup) considering the ratio of allowance set-up and processing time in the scheduling horizon, which improves the weighted modified operation due date rule. [ABSTRACT FROM AUTHOR]

This paper investigates a three-competing group scheduling problem on serial-batching machines considering the setup time of groups and batches, as well as the job-dependent deteriorating effect, where the setup time of groups and batches depends on their own corresponding start time and deterioration rate, and the jobs' actual processing time depends on their starting time and deterioration rate. In this problem, the jobs in three groups are processed competitively, and the jobs belonging to the same group are processed together on a machine, meanwhile, the jobs from each group are divided into batches. The objective is to minimize the makespan of one group with deterioration effect under the constraint of satisfying the threshold value of another group. Some key structural properties are proposed under the relevant demonstration, and a decision flow chart of scheduling rules is constructed based on these structural properties. Then, an effective improved differential evolution (DE) search algorithm combining the shaking operation from variable neighborhood search is developed to solve the studied scheduling problem. Computational experiments are conducted to evaluate the performance of proposed improved DE algorithm and some other well-known algorithms. The experimental results show that the proposed algorithm is more effective and stable than compared algorithms. [ABSTRACT FROM AUTHOR]

In this paper, the problem of minimising maximum completion time on a single batch processing machine is studied. A batch processing is performed on a machine which can simultaneously process several jobs as a batch. The processing time of a batch is determined by the longest processing time of jobs in the batch. The batch processing machine problem is encountered in many manufacturing systems such as burn-in operations in the semiconductor industry and heat treatment operations in the metalworking industries. Heuristics are developed by iterative decomposition of a mixed integer programming model, modified from the successive knapsack problem by Ghazvini and Dupont (1998, Minimising mean flow times criteria on a single batch processing machine with non-identical jobs sizes. International Journal of Production Economics 55: 273–280) and the waste of batch clustering algorithm by Chen, Du, and Huang (2011, Scheduling a batch processing machine with non-identical job sizes: a clustering perspective. International Journal of Production Research 49 (19): 5755–5778). Experimental results show that the suggested heuristics produce high-quality solutions comparable to those of previous heuristics in a reasonable computation time. [ABSTRACT FROM AUTHOR]

We study the scheduling problem of minimising weighted completion times on parallel identical batching machines with dynamic job arrivals and incompatible job families. Each job is associated with a family, weight (priority), release time, and size. Batching machines can process simultaneously up to a specified total size of the jobs of a particular family. The scheduling problem can be represented by. We present a mathematical model and heuristic algorithms employing different local search procedures individually and sequentially under a variable neighbourhood search scheme. We have shown that among local searches, repositioning the batches instead of jobs yields better results. The best-performing heuristic algorithm is capable of generating solutions within 0.6% of the best overall heuristic solution for each instance in a reasonable amount of time. When this heuristic is compared against the mathematical model, solutions that are 3.7% above optimal on average in the 15-job problem instances are possible. [ABSTRACT FROM PUBLISHER]

This study is inspired by a batch scheduling problem in metal working industry which guarantees to satisfy a due date as a commitment to customers. Actual flowtime adopts the backward scheduling approach and considers the due date. Using the actual flowtime as the objective means that the solution is oriented to satisfy the due date, and simultaneosly to minimize the length of time of the parts spending in the shop. This research is to address a problem of scheduling batches consisting of multiple items of parts processed on a batch processor where the completed parts must be delivered several time at different due dates. We propose an algorithm to solve the problem.

To ensure the competitiveness of manufacturing companies in the market, batching and batch scheduling are among the most important tasks. This paper presents a simulation-optimization approach that combines the discrete event simulation (DES) and the genetic algorithm (GA) to solve the batching and batch scheduling problem in a hybrid flow shop (HFS). HFS is widely used for the production of medium and large quantities of different technologically complex products. Based on a real-world manufacturing company, the HFS simulation model was developed using the Tecnomatix Plant Simulation software package. By analysing the influencing factors that represent production costs, a new formulation of the total cost of production was proposed. The purpose of this case study was to ensure timely delivery and minimize production costs by integrating simulation and optimization tools. This research considers sequence-dependent setup times, and availability of manufacturing and transportation equipment. The results of this research showed that the proposed simulation-optimization approach can be applied to solve the problem in many industrial case studies. [ABSTRACT FROM AUTHOR]

Purpose: This paper aims to investigate simultaneous problems of batch scheduling and operator assignment with time-changing effects caused by learning and forgetting. Design/methodology/approach: A mathematical model was developed for the problems, and the decision variables of the model were operator assignment, the number of batches, batch sizes and the schedule of the resulting batches. A proposed algorithm worked by trying different number of batches, starting from one, and increasing the number of batches one by one until the objective function value did not improve anymore. Findings: We mathematically and numerically show that the closest batch to the due date always became the largest batch in the schedule, and the faster operators learn, the larger the difference between the closest batch to the due date and the other batches, the lower optimal number of batches, and the lower the total actual flow time. Originality/value: Previous papers have considered the existence of alternative operators but have not considered learning and forgetting, or have considered learning and forgetting but only in a single-stage system and without considering alternative operators. [ABSTRACT FROM AUTHOR]

We describe the development of a decision-support tool to assist in the operations of a large concentrated apple and pear juice plant. The tool's objective is to generate detailed schedules of clarified juice batches to be produced in the following weeks considering incoming fruit forecasts, commercial commitments, and infrastructural constraints. The tool is based on two interactive modules, PLANNER and SIMOPT, with different and complementary purposes. Each module is based on mixed-integer models with specific inputs, outputs, and user interfaces. PLANNER consists of three submodules: (i) planning assigns a batch of concentrated juice to be produced on a specific day, taking into account cleaning activities, rest days, raw material availability, and production and storage constraints; (ii) preprocessing organizes juice orders in batches; and (iii) pooling provides a detailed monitoring of semielaborated juice in storage pools in terms of inventories and sugar and acid content. Finally, SIMOPT provides a detailed optimal operative condition of the plant together with a thorough calculation of specific costs. This information is used by PLANNER to evaluate the corresponding economic objective functions. Besides providing optimal target conditions to the plant and feasible production schedules, the developed tools generate production guidelines in the long term and allow performing scenario studies. [ABSTRACT FROM AUTHOR]

This paper addresses a batch scheduling problem for a three-stage hybrid flowshop consisting of a machining stage processing common and unique components on unrelated parallel machines, an assembly stage combining the components into assembled products with complex assembly structures, and a differentiation stage processing the assembled products on dedicated machines to produce different product types. The common components are the same for all products and are processed in batches, while the unique components are dedicated to respective given product types and are processed individually (one-by-one component). The goal is to schedule all the products with different assembly structures to minimize total actual flow time (TAFT) defined as total time interval of components to be processed from their arrival times to their common due date. A non-linear programming model is proposed, where small size problems can be solved optimally using the LINGO software, and large size problems is to be solved using a heuristic algorithm. The proposed algorithm consists of two sub-algorithms. The first one is constructed using a shortest processing time (SPT) based heuristic to get a job sequence as an initial solution and the second one is to improve the initial solution using the variable neighbourhood descent (VND) method with neighbourhood insert and swap move operators. In solving the problem with the algorithm, two scenarios arise, e.g., the same and the different sequences for all stages. A set of hypothetical data is generated for different hierarchical assembly structures to test the model and the algorithm, and the results show that the different sequences for all stages obtain solutions with better performances than the same ones. [ABSTRACT FROM AUTHOR]

The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature. [ABSTRACT FROM PUBLISHER]

New mixed-integer programming models are proposed for deterministic batch or cyclic scheduling in flow shops with parallel machines and finite in-process buffers. Models for scheduling with all machines continuously available for processing throughout the entire scheduling horizon as well as for scheduling with an arbitrary pattern of machine availability due to pre-scheduled downtime events are provided. Numerical examples modelled after real-world flexible flow shop scheduling in electronics manufacturing are presented, and to compare the batch and cyclic schedules with continuous or with limited machine availability, results of computational experiments are reported. [ABSTRACT FROM AUTHOR]

We analyse the problem of minimising the mean cycle time of a batch processing stage containing K > 1 batch processors in parallel with incompatible job families and future job arrivals. We provide an integer linear programming formulation and a dynamic program formulation for small problem instances. For larger problem instances, we propose an online heuristic policy MPC_REPEAT. At each instance a decision has to be made, MPC_REPEAT decomposes the problem of simultaneously assigning multiple batches to multiple processors into sequentially assigning multiple batches to multiple processors. When job families are uncorrelated, we show via simulation experiments that MPC_REPEAT has significantly lower mean cycle time than a previously proposed look-ahead method except when: (MPC_REPEAT ignores some job families AND the traffic intensity is high.) Our experiments also reveal that increasing the job family correlation of consecutive job arrivals results, with a few exceptions, in a mean cycle-time reduction, for both policies evaluated. This reduction in cycle time generally increases with: increasing number of job families, decreasing number of processors, and increasing time between job arrivals. Our findings imply that controlling the upstream processors, such that job families of consecutive job arrivals are correlated, can reduce the cycle time at the batch processing stage. Furthermore, the expected mean cycle time reduction due to this strategy can be substantially larger than that expected from switching to a more complex batch processing stage policy, under less stringent conditions. [ABSTRACT FROM PUBLISHER]

This paper proposes an efficient heuristic algorithm for solving a complex batching and scheduling problem in a diffusion area of a semiconductor plant. Diffusion is frequently the bottleneck in the plant and also one of the most complex areas in terms of number of machines, constraints to satisfy and the large number of lots to manage. The purpose of this study is to investigate an approach to group lots in batches and to schedule these batches on machines. The problem is modelled and solved using a disjunctive graph representation. A constructive algorithm is proposed and improvement procedures based on iterative sampling and Simulated Annealing are developed. Computational experiments, carried out on actual industrial problem instances, show the ability of the iterative sampling algorithms to significantly improve the initial solution, and that Simulated Annealing enhances the results. Furthermore, our algorithm compares favourably to an algorithm reported in the literature for a simplified version of our problem. The constructive algorithm has been embedded in software and is currently being used in a semiconductor plant. [ABSTRACT FROM AUTHOR]

We present a method to minimise the cost of batch schedules for a pipe manufacturing facility. The method determines the sequence of production and start date of the batch considering raw material and finished goods holding cost, late delivery cost, and changeover. Our approach is designed to interface to the company's manufacturing execution system, and uses a simplified model of the production line for speed of execution. We demonstrate that methodology results in significant cost savings when compared to existing schedules. [ABSTRACT FROM AUTHOR]

The issue of energy has emerged as one of the greatest challenges facing mankind. In an industrial perspective, the development of site utility systems (generally combined heat and power (CHP) systems) for the generation and management of utilities provides a great potential source for energy savings. However, in most industrial sites, a master–slave relationship usually governs this kind of system and limits the potential operating capacity of CHP. To improve the decision-making process, Agha et al. (2010. Integrated production and utility system approach for optimising industrial unit operation. Energy, 35, 611–627) have proposed an integrated approach that carries out simultaneous and consistent scheduling of batch production plants and site utility systems. The modelling of the problem relies on a mixed integer linear programming (MILP) formulation. Nevertheless, although it is a powerful mathematical tool, it still remains difficult to use for non-expert engineers. In this framework, a graphical formalism based on existing representations (STN, RTN) has been developed: the extended resource task network (ERTN). Combined with an efficient and generic MILP formulation, it permits various kinds of industrial problems, including production and consumption of utility flows to be modelled homogenously. This paper focuses on the semantic elements of the ERTN formalism and illustrates their use through representative examples. [ABSTRACT FROM PUBLISHER]

We study the allocation of machines in a job shop environment to groups of jobs so as to obtain a collection of disjoint production lines minimising the overall cycle time. Jobs are often grouped according to similarities based on functionality or production process, but in some settings it makes more sense to group jobs according to batch size to exploit differences in setup and run times among technologies and machine types. We formulate a model to find an optimal group partition of jobs and an optimal assignment of machines to groups. We show that the problem is [image omitted]hard and formulate a heuristic based on genetic algorithms to find approximate solutions. [ABSTRACT FROM AUTHOR]

This paper presents a comprehensive framework for the strategic capacity expansion of production equipment in semiconductor manufacturing, and the proposed approach is applied to a model of an actual wafer fabrication facility. It is the intention of this work to show that, once intelligently integrated, an analytical queueing model and a numeric computer simulation model can be used synergistically and can lead to a better alternative method than methods restricted to only one of them. The outcome of our methods is a number of good system configurations, each of which is characterised by its cycle time (CT)-throughput (TH) profile. Such profiles fully describe the system's comprehensive performance over a wide range of demand scenarios (involving varying product mix), and hence can be used to thoroughly evaluate alternative configurations in capacity expansion decisions. [ABSTRACT FROM AUTHOR]

Batch processor scheduling, where machines can process multiple jobs simultaneously, is frequently harder than its unit-capacity counterpart because an effective scheduling procedure must not only decide how to group the individual jobs into batches, but also determine the sequence in which the batches are to be processed. We extend a previously developed genetic learning approach to automatically discover effective dispatching policies for several batch scheduling environments, and show that these rules yield good system performance. Computational results show the competitiveness of the learned rules with existing rules for different performance measures. The autonomous learning approach addresses a growing practical need for rapidly developing effective dispatching rules for these environments by automating the discovery of effective job dispatching procedures. [ABSTRACT FROM AUTHOR]

This paper examines scheduling in a manufacturing system with transfer batches. Transfer batches are considered as different batches although they stem from the same job. Genetic algorithms determine the size of the transfer batches for each job and the final schedule with a makespan criterion. A novelty of the genetic algorithm developed is twin chromosome encoding, the first chromosome representing the relative size (participation ratio) of each transfer batch with respect to the whole batch; and the second chromosome applying in effect a dynamic heuristic dispatching rule representation for resolving operation antagonism. New crossover and mutation operators were employed for the first chromosome and standard operators for the second. The genetic algorithms were coded in C++ for better control. A 20 job × eight machine shop was used as a test case. Results favour genetic algorithms over heuristic procedures, but the latter close the gap with an increase in the number of transfer batches. Design of Experiments was used to focus on the most promising genetic algorithm parameter value combinations. [ABSTRACT FROM AUTHOR]

With the advent of the Just-In-Time (JIT) manufacturing philosophy, scheduling problems with delivery performance have received significant attention in recent years. The JIT concept requires not only a penalty for lateness but also for earliness and therefore both early and tardy deliveries are highly discouraged. In this paper, the dynamic scheduling of a single batch processing machine has been addressed for controlling the delivery performance between earliness and tardiness measures. A Look Ahead Batching (LAB) strategy has been proposed. In LAB, the scheduling decisions are made considering the arrival epochs and due dates of the incoming lots, which are easily predictable in a computer-integrated manufacturing environment, especially in the semiconductor industry. LAB strategy is used to control the delivery performance, which involves a trade-off between the conflicting objectives of minimizing earliness- and tardiness-related measures simultaneously. The potential of LAB strategy in controlling delivery performance is demonstrated by an extensive simulation study. [ABSTRACT FROM AUTHOR]

Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination in hierarchical spaces, namely Balanced-Flow Path Network Planning (BF-PNP) problem, and prove its NP-completeness. To balance the flow rate among the layers in the space, we propose a batch scheduling algorithm with the objective of minimizing the scheduling time consumption. To evaluate the performance on efficiency and time complexity, we perform a series of simulations and the results indicate the advantages of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The monitoring of the computational processes in highly distributed environments remains challenging in today's High Performance Computing. In this paper, we define the agent-based cloud monitoring system for supporting the computational tasks scheduling and resource allocation. The system consists of two types of agents, which may decide about the initialization of the schedule execution and monitor the work of the cloud computational nodes. The decision about running the new scheduling process is based on the expected number of available computational units in the specified time window. The efficiency of the proposed MAS-based model was justified through 40 empirical tests, where clouds without and within the MAS support were compared. The multiagent system (MAS) effectiveness has been expressed in the average number of floating point operations completed at the cloud resources in one second. The obtained results show the importance of setting the optimal initial time for execution of the new schedule. Our experiments show that for running the new schedule, at least 25% of the computing units in the clouds should be in the idle mode. Also the batches of tasks should not be too large, cause the waiting time for new schedule for execution should be short and not greater than 10% of expected batch execution time. [ABSTRACT FROM AUTHOR]

Large scale batch scheduling problems with complex constraints are difficult and time-consuming to solve. Therefore, this paper addresses the green batch scheduling problem on non-identical parallel machines with time-of-use electricity prices. The objective of the problem is to minimise total electricity costs (TEC) in production. Two kinds of algorithms—single-population genetic algorithms (SPGA) and multi-population genetic algorithm (MPGA)—are proposed to solve the problem. In the algorithms, the products are allocated into batches and are then allocated to machines randomly. A greedy strategy is designed to arrange the production sequence and the starting time of the batches. Furthermore, a self-adaptive parameter adjustment strategy is proposed to enhance the adaptability of the algorithm. Computational experiments with CPLEX solver have been conducted to evaluate the performance of the algorithms. On small instances, both SPGA and MPGA can achieve approximate results compared with those obtained by CPLEX, and can also achieve smaller TEC on large instances with less computing time. In addition, the proposed MPGA implemented by parallel computing outperforms SPGA in getting better results with nearly the same computing time. [ABSTRACT FROM AUTHOR]

Cloud computing has gained enormous popularity for on-demand services on a pay-per-use basis. However, a single data center may be limited in providing such services, particularly in the peak demand time as it may not have unlimited resource capacity. Therefore, multi-cloud environment has been introduced in which multiple clouds can be integrated together to provide a unified service in a collaborative fashion. However, task scheduling in such environment is much more challenging than that is used in the single cloud environment. In this paper, we propose three allocation-aware task scheduling algorithms for a multi-cloud environment. The algorithms are based on the traditional Min-Min and Max-Min algorithm and extended for multi-cloud environment. All the algorithms undergo three common phases, namely matching, allocating and scheduling to fit them in the multi-cloud environment. We perform extensive simulations on the proposed algorithms and test with various benchmark and synthetic datasets. We evaluate the performance of the proposed algorithms in terms of makespan, average cloud utilization and throughput and compare the results with the existing algorithms in such system. The comparison results clearly demonstrate the efficacy of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP-complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan.

We address the single-machine batch scheduling problem with the objective of minimizing the total setup cost. This problem arises when there are n jobs that are partitioned into F families and when setup operations are required whenever the machine switches from processing a job of one family to processing a job of another family. We assume that setups do not require time but are associated with a fixed cost which is identical for all setup operations. Each job has a processing time and an associated deadline. The objective is to schedule all jobs such that they are on time with respect to their deadlines and the total setup cost is minimized. We show that the decision version of this problem is NP-complete in the strong sense. Furthermore, we present properties of optimal solutions and an O(nlogn+nF) algorithm that approximates the cost of an optimal schedule by a factor of F. The algorithm is analyzed in computational tests. [ABSTRACT FROM AUTHOR]

Despite a great deal of research into precast production scheduling published in academic journals worldwide, little attention has been given to environmental performance related to precast construction transportation and assembly scheduling problems. To address this issue, this paper studies the Just-in-Time (JIT) strategy for supply chain management of precast construction while considering time-dependent transportation time and on-site assembly time. There are two main contributions of our work. First, our analysis expands the current batch-scheduling model of minimizing earliness/tardiness penalties, by incorporating environmental impact considering the time-dependent transportation time and economic impact of resources wasted by waiting for on-site assembly. Second, we quantify the economic and environmental performance using our research objective, consisting of earliness/tardiness penalties, an additional transportation time penalty, and a resource waste penalty. The optimal results show that, compared with the supplier's intuitive minimax optimization with deliveries on the earliest due date, there is an average 10.7% reduction of the objective value of a one-day assembly task by our proposed method. The results also show that the objective of achieving additional environmental performance conflicts with that of obtaining economic performance. However, sensitivity analysis further shows it is not always true to consider only additional environmental performance for the suppliers to achieve ‘green’ value. For a sustainable business, the customer's service-JIT delivery should also be considered. Thus, when the policy makers assign importance weights to different objectives, they should fully consider both the economic and environmental impacts. The research contributes to batch delivery theory by expanding the approach to a time-dependent delivery model by considering both the economic and environmental effects. The method developed is of practical value for precast building projects to help in the successful implementation of sustainable development. [ABSTRACT FROM AUTHOR]

Purpose: Today's manufacturing facilities are challenged by highly customized products and just in time manufacturing and delivery of these products. In this study, a batch scheduling problem has been addressed to enable on-time completion of customer orders in a lean manufacturing environment. The problem is optimizing the partitioning of product components into batches and scheduling of the resulting batches where each customer order is received as a set of products made of various components. Design/methodology/approach: Three different mathematical models for minimization of total earliness and tardiness of customer orders are developed to provide on-time completion of customer orders and also, to avoid excess final product inventory. The first model is a non-linear integer programming model whereas the second is a linearized version of the first. Finally, to solve larger sized instances of the problem, an alternative linear integer model is presented. Findings: Computational study using a suit set of test instances showed that the alternative linear integer model is able to solve all test instances in varying sizes within quite shorter computer times compared to the other two models. It has also been showed that the alternative model is able to solve moderate sized real-world problems. Originality/value: The problem under study differentiates from existing batch scheduling problems in the literature owing to the inclusion of new circumstances that are present in real-world applications. Those are: customer orders consisting of multi-products made of multi-parts, processing of all parts of the same product from different orders in the same batch, and delivering the orders only when all related products are completed. This research also contributes to the literature of batch scheduling problem by presenting new optimization models. [ABSTRACT FROM AUTHOR]

This paper focuses on the batch scheduling problem in multihybrid cell manufacturing systems (MHCMS) in a dual-resource constrained (DRC) setting, considering skilled workforce assignment (SWA). This problem consists of finding the sequence of batches on each cell, the starting time of each batch, and assigning employees to the operations of batches in accordance with the desired objective. Because handling both the scheduling and assignment decisions simultaneously presents a challenging optimization problem, it is difficult to solve the formulated model, even for small-sized problem instances. Three metaheuristics are proposed to solve the batch scheduling problem, namely the genetic algorithm (GA), simulated annealing (SA) algorithm, and artificial bee colony (ABC) algorithm. A serial scheduling scheme (SSS) is introduced and employed in all metaheuristics to obtain a feasible schedule for each individual. The main aim of this study is to identify an effective metaheuristic for determining the scheduling and assignment decisions that minimize the average cell response time. Detailed computational experiments were conducted, based on real production data, to evaluate the performance of the metaheuristics. The experimental results show that the performance of the proposed ABC algorithm is superior to other metaheuristics for different levels of experimental factors determined for the number of batches and the employee flexibility. [ABSTRACT FROM AUTHOR]

This study is inspired by a batch scheduling problem in metal working industry which guarantees to satisfy a due date. The actual flowtime adopts the backward scheduling approach and considers the due date. Using the actual flowtime as the objective, means that the solution is oriented to satisfy the due date, and simultaneosly to minimize the length of time of the parts spending in the shop. This research is to address a problem of scheduling batches consisting of multiple items of parts processed on a batch processor where the completed parts must be delivered several time at different due dates. We propose an algorithm maximize the utilization of the batch processor and to schedule the resulting batches in backwardly non increasing batch size. [ABSTRACT FROM AUTHOR]

We present in this study an algorithmic framework of an intelligent scheduling system that aims to provide an optimum planning for the production process of cutting tools taking into consideration the constraining conditions such as production characteristics, capacity, and performance criteria. Once blunt, cutting tools are sent to the sharpening service composed of parallel machines capable of sharpening more than one tool at the same time. After sharpening, tools are sent back to the departments of origins to be used in other production processes. Thus, any delay in the sharpening service provokes delays in other departments. We develop first a genetic algorithm enhanced by a dynamic programming procedure capable of optimally scheduling a given job sequence. Then we develop a branch and bound method that emulates at each node possible decisions based on a postpone or schedule strategy. Numerical results show that both methods give high quality solutions for the scheduling of tool sharpening operations. Beside the minimization of total tardiness, many other types of decision making related to minimal operation time of a sharpening service, minimal amount of cutting tool inventory and the number of required sharpening machines can be deduced thanks to applying our models. [ABSTRACT FROM AUTHOR]

Time-of-use (TOU) electricity pricing provides new opportunity for power-intensive users to reduce their electricity costs. In order to achieve optimal economic scheduling under TOU pricing for batch production, there are difficulties existed because batch production loads are not fixed or directly adjustable but closely related with time and machine dependant production schedule. Provided that production capacity is abundant and minimizing makespan is not the primary target, a MILP model that integrates batch sizing and scheduling on parallel machines is proposed, in which the objective is to minimize electricity costs in production by utilizing TOU pricing. Use cases are provided to assess the proposed model, experimental results show that the proposed model reduce electricity costs significantly, and promote peak load regulation of power grid. [ABSTRACT FROM AUTHOR]

This paper presents an overview of techniques developed to improve energy efficiency of grid and cloud computing. Power consumption models and energy usage proles are presented together with energy efficiency measuring methods. Modeling of computing dynamics is discussed from the viewpoint of system identication theory, indicating basic experiment design problems and challenges. Novel approaches to cluster and network-wide energy usage optimization are surveyed, including multi-level power and software control systems, energy-aware task scheduling, resource allocation algorithms and frameworks for backbone networks management. Software-development techniques and tools are also presented as a new promising way to reduce power consumption at the computing node level. Finally, energy-aware control mechanisms are presented. In addition, this paper introduces the example of batch scheduler based on ETC matrix approach.

We considered the online scheduling problem of simple linear deteriorating job families on m parallel batch machines to minimize the makespan, where the batch capacity is unbounded. In this paper, simple linear deteriorating jobs mean that the actual processing time p j of job J j is assumed to be a linear function of its starting time s j , i.e., p j = α j s j , where α j > 0 is the deterioration rate. Job families mean that one job must belong to some job family, and jobs of different families cannot be processed in the same batch. When m = 1 , we provide the best possible online algorithm with the competitive ratio of ( 1 + α max ) f , where f is the number of job families and α max is the maximum deterioration rate of all jobs. When m ≥ 1 and m = f , we provide the best possible online algorithm with the competitive ratio of 1 + α max .

In this study, a batch scheduling with job grouping and batch sequencing is considered. A clustering algorithm and dispatching rule selection model is developed to minimize total tardiness. The model and algorithm are based on the constrained k-means algorithm and neural network. We also develop a method to generate a training dataset from historical data to train the neural network. We use numerical examples to demonstrate that the proposed algorithm and model efficiently and effectively solve batch scheduling problems.

We study a special two-stage flexible flowshop, which consists of several parallel identical machines in the first stage and a single machine in the second stage. We assume identical jobs, and the option of batching, with a required setup time prior to the processing of a new batch. We also consider the option to use only a subset of the available machines. The objective is minimum makespan. A unique optimal solution is introduced, containing the optimal number of machines to be used, the sequence of batch sizes, and the batch schedule. The running time of our proposed solution algorithm is independent of the number of jobs, and linear in the number of machines