Search

The 1 | s-batch (∞) , r j | ∑ w j U j scheduling problem takes as input a batch setup time Δ and a set of n jobs, each having a processing time, a release date, a weight, and a due date; the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy (Oper Res Lett 16(2):79–86, 1994); as a wide generalization of Knapsack, it is NP -hard. In this work, we provide a multivariate complexity analysis of the 1 | s-batch (∞) , r j | ∑ w j U j problem with respect to several natural parameters. That is, we establish a classification into fixed-parameter tractable and W [ 1 ] -hard problems, for parameter combinations of (i) # p = number of distinct processing times, (ii) # w = number of distinct weights, (iii) # d = number of distinct due dates, (iv) # r = number of distinct release dates. Thereby, we significantly extend the work of Hermelin et al. (Ann Oper Res 298:271–287, 2018) who analyzed the parameterized complexity of the non-batch variant of this problem without release dates. As one of our key results, we prove that 1 | s-batch (∞) , r j | ∑ w j U j is W [ 1 ] -hard parameterized by the number of distinct processing times and distinct due dates. To the best of our knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that 1 | s-batch (∞) , r j | ∑ w j U j is fixed-parameter tractable parameterized by # d + # p + # r , and parameterized by # d + # w if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b. [ABSTRACT FROM AUTHOR]

This paper studies a two-agent scheduling problem on mixed batch machines in parallel. A mixed batch machine can process several jobs simultaneously as a batch, as long as the number of jobs in the batch does not exceed the machine capacity. The processing time of a mixed batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective is to minimise the weighted sum of two agents' makespans. We present four approximation algorithms based on two strategies: the machine-centric strategy and the agent-centric strategy. For each strategy, a full batch longest processing time (FBLPT) rule and a longest processing time greedy (LPTG) rule are used. We conduct theoretical analyses based on the worst-case performance ratio to provide the provable guarantees on the performances of the algorithms, and simulation analyses based on randomly generated instances to evaluate the average performances of the algorithms. Furthermore, we verify the consistency between the theoretical and simulation results. The algorithms using agent-centric strategy perform better than ones using machine-centric strategy. Finally, we provide managerial insights for the problem by analysing the technological parameters of batches, importance of agents, and demand seasonality. [ABSTRACT FROM AUTHOR]

We consider online parallel-batch scheduling of f incompatible unit-length job families with variable lookahead interval to minimize the maximum completion time, where f is the number of job families which is known in advance. Incompatible job family means that a batch only contains the jobs from the same job family. At any time t , an online algorithm can foresee the information of the jobs arriving in the time interval (t , t + Δ (t) ] , where Δ (t) = (λ − 1) t + β is variable. When the batch capacity b = ∞ and f ≥ 1 , we provide a best possible online algorithm with competitive ratio 1 + α f for 0 ≤ β < 1 and 1 ≤ λ ≤ 1 + β , where α f is a positive root of λ f α f 2 + (λ f + β + 1 − f) α f + β − f = 0. When the batch capacity (f <) b < ∞ and f ≥ 2 , we give an online algorithm with competitive ratio 1 + max { f f α f + f , f λ f α f + β + 1 } for 0 ≤ β < 1 and λ ≥ 1 , and prove that it is the best possible for λ = 1 and 0 ≤ β ≤ f + 1 − f 2 + 1 2 . [ABSTRACT FROM AUTHOR]

This paper addresses a parallel machine scheduling problem with non-anticipatory family setup times and batching, considering the task's stochastic processing times and release dates. The problem arises from a real-life ship scheduling problem in the oil and gas industry. We developed an Iterated Greedy simheuristic with built-in Monte Carlo Simulation to sample the stochastic parameters. We conducted experiments on a set of instances from the literature, considering two simheuristic variants and three uncertainty levels for the stochastic parameters. To highlight the advantages of using simulation to tackle the stochastic problem, the simheuristics are compared against a regular Iterated Greedy metaheuristic, yielding an improvement of up to 16.5% on the objective function's expected values, with a reduced impact on computational times. During a risk analysis, the Pareto set of solutions is generated to illustrate the trade-off between the expected objective value of the solutions and the conditional value at risk, providing decision-makers with a useful tool to select the schedules that better fit their risk profiles. We use an iterative mechanism to build confidence intervals within a certain confidence level during the method's simulation step, interrupting the procedure when it reaches the desired error. This strategy's advantage is highlighted in the computational experiments, which indicates that the number of replications of the simulation is instance and uncertainty level dependent. A periodic re-planning strategy is also used to evaluate the performance of the simheuristic, highlighting the advantages of using the proposed algorithm in a real-life usage situation. [ABSTRACT FROM AUTHOR]

This paper presents the problem of batching and scheduling jobs belonging to incompatible job families on unrelated-parallel machines. More specifically, we investigate cost-efficient approaches for solving batching and scheduling problems concerning the desired lower bounds on batch sizes ( LB b ), which indirectly has a considerable impact on the production cost. Batch scheduling is a more realistic extension of the traditional group scheduling approach, in which the jobs belonging to a job family can be processed as multiple batches. The objective is to minimize the total weighted job completion time and tardiness subject to a machine- and sequence-dependent setup time, dynamic machine availability and job release times, customer segments and job priority, and different machine capability and eligibility criteria for processing. Solving this type of batch scheduling problem is a big challenge due to the high computational complexity incurred by both the sequencing assignment and batching composition. A machine learning random forest classification algorithm is used for the LB b determination. Then, an efficient mixed-integer linear programming model (MILP) is developed based on the flow conservation constraints of jobs on machines to reduce the computational complexity. By mapping the MILP model onto a network formulation, an equivalent integer set partitioning type formulation is developed for a branch-and-price optimization algorithm. Computational experiments carried out over different sets of instances, indicate the efficiency and effectiveness of the optimization algorithm, compared to the linear relaxation and relaxed MILP models. Regarding the only available benchmark in the literature, the optimization algorithm yields optimal solutions with affordable computational time. [ABSTRACT FROM AUTHOR]

In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution. [ABSTRACT FROM PUBLISHER]

• A MILP model for the DRHHFBSP is developed. • A construction heuristic capable of generating excellent solutions is developed. • An iterative construction-local search-reconstruction algorithm is designed. In recent years, the distributed hybrid flowshop scheduling problem (DHFSP) has garnered widespread attention due to the continuous emergence of practical challenges. The production model, characterized by multiple varieties and small batches, is widely observed in the industrial sector. Additionally, in various real-world scenarios, batches often undergo repeated processes across multiple stages. This paper addresses the research gap by introducing the reentrant nature of batches and the heterogeneity of factories into the DHFSP, resulting in a novel problem referred to as the distributed reentrant heterogeneous hybrid flowshop batch scheduling problem (DRHHFBSP). To tackle this problem, we propose a mixed-integer linear programming (MILP) model. Given that this problem falls into the NP-hard category, an iterative construction-local search-reconstruction algorithm (ICLSRA) is designed. Specifically designed by incorporating construction, local search, and reconstruction processes that have different roles, this algorithm strikes a balance between local and global search. Comparative analysis with the MILP model and state-of-the-art algorithms demonstrates the superiority of ICLSRA in achieving efficient solutions for the DRHHFBSP. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This research addresses a batch scheduling problem for single item parts with multi due date on m heterogeneous batch processors. The objective is to minimise total actual flowtime of parts through the shop. The total actual flowtime of parts in a batch is the multiplication of the interval between batch arrival time and the due date by the number of parts in the batch. Using the actual flowtime as the objective means it is oriented to satisfy the due date as a commitment to customers, and simultaneously to minimise the length of time of the parts spending in the shop. An algorithm to solve this problem is proposed. [ABSTRACT FROM AUTHOR]

Copyright of Control Theory & Applications / Kongzhi Lilun Yu Yinyong is the property of Editorial Department of Control Theory & Applications and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This study addresses the issue of scheduling batch machine to minimize total tardiness. Vacuum heat treatment allows multiple jobs to be processed as a batch, as long as they do not exceed the machine's weight and size limits; the weight and size of the jobs both impact the batch processing time. By considering the differences in the release time and due date for each job, a mixed-integer linear programming model is developed and validated using small-scale instances. To tackle large-scale scheduling problems, an intelligent algorithm based on deep reinforcement learning is proposed. Double deep Q-learning networks are designed, and the environmental state feature matrix is extracted as input parameters for the networks. Four job-sorting rules and three scheduling time windows are defined, resulting in twelve action rules within the action space. The most suitable action rule is dynamically selected based on the current batch's environmental status during the scheduling process. Through extensive comparison using large-scale random data, the proposed algorithm demonstrates significantly improved scheduling performance compared to the benchmark algorithms. • A new mixed-batch scheduling problem involves batch times influenced by job weight/size, constrained by machine weight/size. • An intelligent algorithm based on DRL (Deep Reinforcement Learning) was proposed to address batch scheduling problems. • Double deep Q-learning networks were designed, with environmental state feature matrix extracted as input for the networks. • Four job sorting rules and three scheduling time windows were defined, yielding twelve action rules in the action space. • Dynamic selection of the most suitable action rule based on the current batch's environmental status during the scheduling. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

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]

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]

Uncertain single machine scheduling problem for batches of jobs is an important issue for manufacturing systems. In this paper, we use uncertainty theory to study the single machine scheduling problem with deadlines where the processing times are described by uncertain variables with known uncertainty distributions. A new model for this problem is built to maximize expected total weight of batches of jobs. Then the model is transformed into a deterministic integer programming model by using the operational law for inverse uncertainty distributions. In addition, a property of the transformed model is provided and an algorithm is designed to solve this problem. Finally, a numerical example is given to illustrate the effectiveness of the model and the proposed algorithm. [ABSTRACT FROM AUTHOR]

This paper addresses an integrated production and delivery batch scheduling problem for a make-to-order environment over daily time period, where the holding costs of in-process and completed parts at a supplier location and of completed parts at a manufacturer location are distinguished. All orders of parts with different due dates from the manufacturer arrive at the same time. The parts are produced in production batches and subsequently the completed parts are delivered in delivery batches using a capacitated vehicle in order to be received at the respective due dates. This study was aimed at finding an integrated schedule of production and delivery batches so as to meet the due date at minimum total cost consisting of the corresponding holding cost and delivery cost. The holding cost is a derivation of the so-called actual flow time (AFT), while the delivery cost is assumed to be proportional to the number of deliveries. The problems can be formulated as an integer non-linear programming model, and the global optimal solution can be obtained using optimization software. A heuristic algorithm is proposed to cope with the computational time problem using software. The numerical experiences show that the proposed algorithm yields near global optimal solutions. [ABSTRACT FROM AUTHOR]

Time-of-use (TOU) electricity pricing has been a common practice to enhance the peak load regulation capability of power grid. Meanwhile, it provides a good opportunity for industries to reduce energy costs, especially for energy-intensive ones, where batch scheduling is often involved. Majority of batch scheduling problems have been proved to be NP-hard, even for most single-machine environments. Optimizing batch scheduling under TOU policy in these industries will be of great significance. Singlemachine batch scheduling is an important basis for more complicated shop scheduling problems. This paper investigates a bi-objective single-machine batch scheduling problem under TOU policy: the first objective is to minimize the makespan and the second is to minimize the total electricity costs. The considered problem is first formulated as a bi-objective mix-integer linear programming (MILP) model and is demonstrated to be NP-hard. Subsequently, the MILP is simplified by analyzing properties and search space for a Pareto optimal solution is greatly reduced. Then, an exact ε-constraint method is adapted to obtain its Pareto front, which is accelerated due to these properties. Finally, a preferable solution is recommended for decision makers via a fuzzy-logic-based approach. Computational results on randomly generated instances show the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

In this paper, we consider a two-agent batch scheduling problem on a single machine such that the processing times of agent 1 and the due date of agent 2 in the same batch are identical. The objective is to minimize the total completion time of agent 1 with a constraint on the maximum tardiness of agent 2. First, we propose the optimality conditions. Then, we show that the problem is strongly NP-hard. Finally, we prove the problem remains NP-hard even for the case with one batch of agent 2, and develop a pseudo-polynomial algorithm and an approximation algorithm for this case. [ABSTRACT FROM AUTHOR]

This paper studies a problem of scheduling fabrication and assembly operations in a two-machine flowshop, subject to the same predetermined job sequence on each machine. In the manufacturing setting, there are n products, each of which consists of two components: a common component and a unique component which are fabricated on machine 1 and then assembled on machine 2. Common components of all products are processed in batches preceded by a constant setup time. The manufacturing process related to each single product is called a job. We address four regular performance measures: the total job completion time, the maximum job lateness, the total job tardiness, and the number of tardy jobs. Several optimality properties are presented. Based upon the concept of critical path and block schedule, a generic dynamic programming algorithm is developed to find an optimal schedule in O( n) time. [ABSTRACT FROM AUTHOR]

Batch scheduling accommodates a group of tasks with the start/end time constraints to maximize the revenue from scheduling tasks over a number of servers, which has been extensively studied in the context of job?machine scheduling. In optical networks, batch scheduling refers to the process of scheduling a group of data units (i.e., the jobs) competing for the same set of wavelength channels (i.e., the machines). Classical job?machine scheduling studies have considered both the case of a pure-loss system, and the case with waiting rooms (i.e., buffers), which are generally in the form of random access memory (RAM). In optical networks, the buffering is achieved by feeding the optical signal into a fixed length of fiber, namely, a fiber delay line (FDL), since optical RAM is not yet available. The unique feature of the discrete and predefined buffering time in fact instantiates a new type of problem, namely, job?machine scheduling with discrete-time buffers. In this work, we comprehensively study batch scheduling in optical networks. We show that batch scheduling with and without FDLs corresponds to two different instances of the job?machine scheduling problem. While proving their NP-completeness, we mathematically model both cases using integer linear programming formulations to provide an optimal scheduling. Given the timeliness request for on-line batch scheduling and the dramatic problem size in optical networks, we also propose polynomial-time heuristic algorithms, which are shown to be near optimal in our simulations. [ABSTRACT FROM PUBLISHER]

Abstract: This paper considers the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makespan and total completion time are given using mixed integer programming method and the computational complexity is analyzed. The bound on the number of feasible solutions is given and the properties of the optimal solutions are presented. Then a polynomial time algorithm is proposed and the worst case ratios for minimizing total completion time and makespan is proved to be 2 and (8/3–2/3m) respectively. To test the proposed algorithm, we generate different levels of random instances. The computational results demonstrate the effectiveness of the algorithm for minimizing the two objectives. [Copyright &y& Elsevier]

We study the optimality of the very practical policy of equal allocation of jobs to batches in batch scheduling problems on an rn-machine open shop. The objective is minimum makespan. We assume unit processing time jobs, machine-dependent setup times and batch availability. We show that equal allocation is optimal for a two-machine and a three-machine open shop. Although, this policy is not necessarily optimal for larger size open shops, it is shown numerically to produce very close-to-optimal schedules. [ABSTRACT FROM AUTHOR]

The problem of minimum makespan on an m machine jobshop with unit execution time (UET) jobs ( m ≥ 3) is known to be strongly NP-hard even with no setup times. We focus in this article on the two-machine case. We assume UET jobs and consider batching with batch availability and machine-dependent setup times. We introduce an efficient \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document} \begin{align*}(O(\sqrt{n}))\end{align*} \end{document} algorithm, where n is the number of jobs. We then introduce a heuristic for the multimachine case and demonstrate its efficiency for two interesting instances. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011 [ABSTRACT FROM AUTHOR]

Abstract: This paper considers a coordinated scheduling problem. For the first-stage transportation there is a crane available to transport the product from the warehouse to a batching machine. For the second-stage transportation there is a vehicle available to deliver the completed jobs from the machine shop floor to the customer. The coordinated scheduling problem of production and transportation deals with sequencing the transportation of the jobs and combining them into batches to be processed. The problem of minimizing the sum of the makespan and the total setup cost was proven by Tang and Gong to be strongly NP-hard. This paper proposes two genetic algorithm (GA) approaches for this scheduling problem, with different result representations. The experimental results demonstrate that a regular GA and a modified GA (MGA) can find near-optimal solutions within an acceptable amount of computational time. Among the two proposed metaheuristic approaches, the MGA is superior to the GA both in terms of computing time and the quality of the solution. [Copyright &y& Elsevier]

flow-shop batching problem with consistent batches is considered in which the processing times of all jobs on each machine are equal to p and all batch set-up times are equal to s. In such a problem, one has to partition the set of jobs into batches and to schedule the batches on each machine. The processing time of a batch B is the sum of processing times of operations in B and the earliest start of B on a machine is the finishing time of B on the previous machine plus the set-up time s. Cheng et al. (Naval Research Logistics 47:128-144, ) provided an O( n) pseudopolynomial-time algorithm for solving the special case of the problem with two machines. Mosheiov and Oron (European Journal of Operational Research 161:285-291, ) developed an algorithm of the same time complexity for the general case with more than two machines. Ng and Kovalyov (Journal of Scheduling 10:353-364, ) improved the pseudopolynomial complexity to $O(\sqrt{n})$ . In this paper, we provide a polynomial-time algorithm of time complexity O(log n). [ABSTRACT FROM AUTHOR]

We propose a novel job scheduling approach for homogeneous cluster computing platforms. Its key feature is the use of virtual machine technology to share fractional node resources in a precise and controlled manner. Other VM-based scheduling approaches have focused primarily on technical issues or extensions to existing batch scheduling systems, while we take a more aggressive approach and seek to find heuristics that maximize an objective metric correlated with job performance. We derive absolute performance bounds and develop algorithms for the online nonclairvoyant version of our scheduling problem. We further evaluate these algorithms in simulation against both synthetic and real-world HPC workloads and compare our algorithms to standard batch scheduling approaches. We find that our approach improves over batch scheduling by orders of magnitude in terms of job stretch, while leading to comparable or better resource utilization. Our results demonstrate that virtualization technology coupled with lightweight online scheduling strategies can afford dramatic improvements in performance for executing HPC workloads. [ABSTRACT FROM AUTHOR]