Search

The use of Additive Manufacturing (AM) technology has largely increased in the last years. Because of its large differences from conventional technologies, the use of AM in production systems might call for new strategies in production planning and control. To this aim, this paper proposes analytical models to predict aggregate performance measures such as flow time, work in process, and production throughput, for production systems characterised by Laser Powder Bed Fusion AM technology. These indicators could be used both in operations strategy development and in technology comparison. The proposed models differentiate for their detail of the analysis and the number of input parameters that need to be estimated. The results show that the level of detail of the model affects the analysis leading to quite different values of the performance measures, especially in the case of highly saturated systems. Also, a discussion about the applicability of the proposed model to other AM technologies show whether and to what extent the proposed models can be applied for modelling other AM technologies. [ABSTRACT FROM AUTHOR]

This survey investigates the field of moderate exponential-time algorithms for N P -hard scheduling problems, i.e., exact algorithms whose worst-case time complexity is moderately exponential with respect to brute force algorithms. Scheduling problems are very challenging problems for which interesting results have emerged in the literature since 2010. We will provide a comprehensive overview of the known results of these problems before detailing three general techniques to derive moderate exponential-time algorithms. These techniques are Sort & Search, Inclusion–Exclusion and Branching. In the last part of this survey, we will focus on side topics such as approximation in moderate exponential time, the design of lower bounds on worst-case time complexities or fixed-parameter tractability. We will also discuss the potential benefits of moderate exponential-time algorithms for efficiently solving in practice scheduling problems. [ABSTRACT FROM AUTHOR]

This paper investigates the single machine group scheduling with unrestricted (different) due date assignments and resource allocations (controllable processing times). The resource allocations mean that the actual job processing times are convex decreasing function of their consumption of resources. To solve the general problem of minimizing the weighted sum of earliness, tardiness, due date assignment cost and resource consumption cost (the weights are job-dependent weights), we propose lower and upper bounds to speed up the search process of the branch-and-bound algorithm. To solve this problem quickly and accurately, we also propose a heuristic algorithm. Computational results are tested to evaluate the performance of the algorithms. [ABSTRACT FROM AUTHOR]

We study single-machine scheduling problems with Generalized due-dates (GDD), learning effect, and optional job rejection. For the GDD setting, the due dates are assigned to the jobs according to their position in the sequence rather than their identity. Thus, assuming that due dates are numbered in non-decreasing order, the jth due date refers to the job assigned to the jth position. The learning effect is a model where completing former jobs decreases the completion time of latter jobs. The processing time is still part of the input, depending on how many jobs have already been scheduled. Allowing the option of job rejection means that not all jobs must be processed. In this case, the scheduler is penalized for each rejected job, and an input parameter bounds the total rejection cost. Two objective functions are considered with the above-mentioned settings: minimizing total tardiness and minimizing maximal tardiness. The problems are polynomially solvable when there is no option for job rejection. Otherwise, both are shown to be NP-hard, pseudo-polynomial dynamic programming solutions are proposed, and numerical experiments are provided. [ABSTRACT FROM AUTHOR]

New solutions for problems in optimal scheduling of activities in a project under temporal constraints are developed in the framework of tropical algebra which deals with the theory and application of algebraic systems with idempotent operations. We start with a constrained tropical optimization problem that has an objective function represented as a vector form given by an arbitrary matrix, and that can be solved analytically in a closed but somewhat complicated form. We examine a special case of the problem when the objective function is given by a matrix of unit rank, and show that the solution can be sufficiently refined in this case, which results in an essentially simplified analytical form and reduced computational complexity of the solution. We exploit the obtained result to find complete solutions of project scheduling problems to minimize the project makespan and the maximum absolute deviation of start times of activities under temporal constraints. The constraints under consideration include “start–start”, “start–finish” and “finish–start” precedence relations, release times, release deadlines and completion deadlines for activities. As an application, we consider optimal scheduling problems of a vaccination project in a medical centre. [ABSTRACT FROM AUTHOR]

Serverless computing is one of the latest technologies that has received much attention from researchers and companies in recent years since it provides dynamic scalability and a clear economic model. Serverless computing enables users to pay only for the time they use resources. This approach has several benefits, including optimizing costs and resource utilization; however, cold starts are a concern and challenge. Various studies have been conducted in the academic and industrial sectors to deal with this problem, which poses a significant research challenge. This paper comprehensively reviews recent cold start research in serverless computing. Hence, this paper presents a detailed taxonomy of several serverless computing strategies for dealing with cold start latency. We have considered two main approaches in the proposed classification: Optimizing Loading Times (OLT) and Optimizing Resource Usage (ORU), each including several subsets. The subsets of the primary approach OLT are divided into container-based and checkpoint-based. Also, the primary approach ORU is divided into machine learning (ML)-based, optimization-based, and heuristic-based approaches. After analyzing current methods, we have categorized and investigated them according to their characteristics and commonalities. Additionally, we examine potential challenges and directions for future research. [ABSTRACT FROM AUTHOR]

In this work, we investigate the online MapReduce processing problem on mm uniform parallel machines, aiming at minimizing the makespan. Each job consists of two sets of tasks, namely, the map tasks and the reduce tasks. A job’s map tasks can be arbitrarily split and processed on different machines simultaneously, while its reduce tasks can only be processed after all its map tasks have been completed. We assume that the reduce tasks are preemptive, but cannot be processed on different machines in parallel. We provide a new lower bound for this problem and present an online algorithm with a competitive ratio of 2−1m2-\frac{1}{m} (mm is the number of machines) when the speeds of the machines are 1.

A single machine scheduling problem takes into account a common due window assignment, including delivery time, resource allocation and learning effect. The basic processing time, position and allotted resources are all linked to the actual processing time. We take into consideration three goal functions, which minimize the costs of earliness, tardiness, start time of window, window size, resource allocation and makespan. The aim is to find the optimal sequence and distribution of resources. Polynomial time algorithms are provided for each of the three issues. The algorithms have O (n 3) levels of complexity, where n is the number of jobs. Special cases with the same learning rates are also considered. Polynomial time algorithms are also provided for each of the special cases. The algorithms have O (n log n) levels of complexity. [ABSTRACT FROM AUTHOR]

In this paper we consider single-machine scheduling problems with group technology, where the group setup times are general linear functions of their starting times and the jobs in the same group have general truncated learning effects. The objective is to minimize the makespan and total completion time, respectively. We show that the makespan minimization remains polynomially solvable. For the total completion time minimization, optimal properties are presented and then we introduce some heuristic algorithms and a branch-and-bound algorithm. [ABSTRACT FROM AUTHOR]

This study investigates the prize-collecting single machine scheduling with bounds and penalties (PC-SMS-BP). In this problem, a set of n jobs and a single machine are considered, where each job J j has a processing time p j , a profit π j and a rejection penalty w j . The upper bound on the processing number is U. The objective of this study is to find a feasible schedule that minimizes the makespan of the accepted jobs and the total rejection penalty of the rejected jobs under the condition that the number of the accepted jobs does not exceed a given threshold U while the total profit of the accepted jobs does not fall below a specified profit bound Π . We first demonstrate that this problem is NP-hard. Then, a pseudo-polynomial time dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS) are proposed. Finally, numerical experiments are conducted to compare the effectiveness of the two proposed algorithms. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of scheduling independent jobs with release dates on identical parallel machines with a single server. The goal consists in minimizing the maximum lateness. This is a realistic extension of the traditional parallel machine scheduling problem with a single server, in which all jobs are assumed to be available at the beginning of the schedule. This problem, referred to as P , S 1 | r j | L max , has various applications in practice. To date, research on it has focused on complexity analysis. To solve small-sized instances of the problem, we present two mixed-integer-programming formulations, along with a valid inequality. Due to the N P -hard nature of the problem, we propose a constructive heuristic and two metaheuristics, namely a General Variable Neighborhood Search (GVNS) and a Greedy Randomized Adaptive Search Procedures, both using a Variable Neighborhood Descent as an intensification operator. In the experiments, the proposed algorithms are compared using a set of new instances generated randomly with up to 500 jobs, in line with the related literature. It turns out that GVNS outperforms by far the other approaches. [ABSTRACT FROM AUTHOR]

This paper considers an unrelated parallel machine scheduling problem with a common due date where the objective is to minimize the sum of completion times, earliness, and tardiness durations of the jobs. This paper discovers some properties of the considered problem for restricted and unrestricted common due dates. By using these properties, the paper shows the existence of some optimal policies for the problem. Furthermore, optimal policies for the problem are found. According to our main findings, optimal policies for the problem are to increase the number of early jobs, to use the shortest processing time dispatching rule for tardy jobs, and to distribute tardy jobs on machines with tardy workloads that differ from each other as much as possible. These strategies for the problem are new to the literature and the problem has the potential to be extended. Using these strategies, the paper presents a novel heuristic algorithm for the problem that is rarely studied in the literature. Furthermore, the proposed heuristic is compared with two existing algorithms by generating some test instances for experimental study. The experimental study shows that the proposed heuristic outperforms other algorithms. Furthermore, the paper discusses which components of our proposed solution approach have impacts on the solution quality. [ABSTRACT FROM AUTHOR]

In this paper, we study the m-machine ( m ≥ 3 ) permutation flow shop scheduling in which the processing time of a job depends not only on the sum of actual processing times of previous jobs but also on its job-dependent truncation parameter, i.e., the general truncated learning effects. The goal is to find a sequence so as to minimize the makespan, we prove that this problem is NP-hard. Two simple heuristics are proposed and their worst-case bounds are presented. We also propose a branch-and-bound algorithm and some heuristics to solve this problem. Further, computational experiments are conducted to determine the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Minimizing the weighted completion time of jobs in the unrelated parallel machines model is a fundamental scheduling problem. The first (3 / 2 - c) –approximation algorithm for this problem, for some constant c > 0 , was obtained in the work of Bansal et al. (SIAM J Comput, 2021). A key ingredient in this work was the first dependent-rounding algorithm with a certain guaranteed amount of negative correlation. We improve upon this guaranteed amount from 1/108 to 1/27, thus also improving upon the constant c in the algorithms of Bansal et al. and Li (SIAM J Comput, 2020) for weighted completion time. Given the now-ubiquitous role played by dependent rounding in scheduling and combinatorial optimization, our improved dependent rounding is also of independent interest. [ABSTRACT FROM AUTHOR]

This paper tackles the two-machine chain-reentrant flow shop scheduling problem with the no-wait constraint; we assume that each job passes from the first machine to the second and returns back to the first machine in order to execute its last operation. The objective is to minimize the makespan. In this work, we prove that the symmetric case of this problem, which is proven to be N P -hard in the strong sense, remains N P -hard. Then we provide two polynomial subproblems. For the main problem’s resolution, we propose two new efficient heuristics as well as two improved lower bounds that consistently outperform the existing methods. Additionally, we provide an effective Branch & Bound algorithm that can solve up to 100 jobs for some types of instances. These contributions not only enhance the theoretical comprehension of the problem but also offer efficient solutions supported by extensive statistical analysis over randomly generated instances. [ABSTRACT FROM AUTHOR]

This paper discusses the single-machine scheduling problems with deteriorating jobs and past-sequence-dependent delivery times. Under the general deterioration function, the objective is to determine an optimal schedule for the job that minimizes the makespan, and the total weighted completion time. We demonstrate that the makespan minimization is polynomially solvable. For the total weighted completion time, this problem is NP-hard, to solve this problem, we provide the branch-and-bound algorithm and some heuristic algorithms. [ABSTRACT FROM AUTHOR]

Under common due window assignment, a single machine scheduling problem with learning effect, delivery time and convex resource allocation is considered. Actual processing time is related to normal processing time, job dependent learning effect and allocated resources. There are three objective functions are considered. They involve earliness, tardiness, due window costs and resource costs with position dependent weights. The first objective function is to minimize the total costs of earliness, tardiness, start time of window, window size and resource allocation; the second objective function is to minimize the total costs of earliness, tardiness, start time of window and window size under resource-limited conditions; the third objective function is to minimize the cost of resource allocation under the scheduling function constraint. The goal is to determine the optimal sequence and resource allocation. All three problems are proved that they can be solved in polynomial time and polynomial time algorithms are given separately. [ABSTRACT FROM AUTHOR]

In order to increase the efficiency of production in a deteriorating environment through competition amongst the individual agents, this study explores a two-agent scheduling problem with one deterioration rate for each job, where the processing time of a job is a function of the position-dependent workload, resource allocation, and deterioration rate (the range of the deterioration rate is non-negative). The optimal processing sequence and resource allocation for the jobs are found by giving an upper bound of an agent to minimize the maximum value of earliness, tardiness and decision variable of another agent under slack due-date assignment. It is verified that the problem cannot be solved in polynomial time, for which various heuristic algorithms and a branch-and-bound algorithm are proposed to simulate the data to find a better range in the deterioration rate parameter. [ABSTRACT FROM AUTHOR]

This paper studies the single machine scheduling problems with truncated logarithm processing times and exponential past-sequence-dependent delivery times. We prove that the makespan and total completion time minimizations are polynomially solvable. For the total weighted completion time minimization, we illustrate that it remains polynomially solvable under a special case; under the general case, this paper proposes heuristic, tabu search and branch-and-bound algorithms. Computational experiments indicate that the heuristic algorithm is more effective than tabu search algorithm. [ABSTRACT FROM AUTHOR]

We devise schemes for producing, in the least possible time, p identical objects with n agents that work at differing speeds. This involves halting the process to transfer production across agent types. For the case of two types of agent, we construct schemes based on the Euclidean algorithm that seeks to minimize the number of pauses in production. [ABSTRACT FROM AUTHOR]

This paper studies the bicriteria problem of non-preemptively scheduling n jobs, each of which is associated with a due date and comprises a standard and a specific component, on a single fabrication machine to minimize makespan and maximum lateness simultaneously. The specific components are processed individually and the standard components are grouped into batches for processing. A setup time is required before each batch of standard components is processed. A standard component is available (i.e., ready for delivery to the next production stage) only when the batch it belongs to is totally completed, whereas a specific component is available on completion of its processing. The completion time of a job is defined as the moment when both its two components have been processed and are available. An O (n 2 log n) -time algorithm with linear memory requirements is presented which can generate all Pareto optimal points and find a corresponding Pareto optimal schedule for each Pareto optimal point. [ABSTRACT FROM AUTHOR]

In light of the growing challenges posed by the variable nature of wind and solar energy outputs alongside the inconsistent patterns of Electric Vehicle (EV) charging, this study introduces a groundbreaking approach to cooperative scheduling between wind-solar energy systems and EVs. Departing from traditional optimization models that primarily concentrate on operational efficiency, our research innovatively incorporates passenger travel preferences into the equation when determining EV charging demands, thereby optimizing renewable energy utilization.Our methodology involves employing a sophisticated optimization strategy that meticulously considers the stochastic behavior of wind and solar resources and unique EV characteristics. This process uses a state-of-the-art scenario construction technique to manage renewable energy uncertainties, complemented by an enhanced fast forward-backward elimination algorithm to efficiently condense the number of scenarios analyzed. We further refine this model by examining the travel behaviors and needs of EV users in a community setting to develop a user satisfaction metric that seamlessly aligns travel convenience with the financial implications of charging and discharging cycles.Significantly, our work has culminated in the establishment of a bi-level optimization framework that simultaneously reduces power system network losses and elevates overall user satisfaction concerning travel experiences. This novel model effectively orchestrates the integration of wind-solar energy outputs with EV charging necessities, thereby enhancing the economic robustness of the power system and ensuring a higher level of consumer satisfaction. Ultimately, this research contributes to the sustainable and efficient operation of future power systems where renewable energy and electric mobility play pivotal roles.

Max–min algebra is defined as a linearly ordered set with two binary operations. Classical addition and multiplication are replaced by maximum and minimum, respectively. A square matrix is called robust, if all its orbits converge to an eigenvector. In practice, matrix inputs and start vector inputs are rather contained in some intervals than exact values. Considering matrices and vectors with interval coefficients is therefore of great practical importance. In this paper, we study a special type of the robustness called the X -robustness, the case when a starting vector is limited by a lower bound vector x _ and an upper bound vector x ¯ . If we consider some components of the interval starting vector with the existential quantifier and others with the general quantifier, two new types of X -robustness arise, called X E A -robustness and X A E -robustness. Using a similar quantification of interval matrix elements, we obtain AE/EA- X E A -robustness and AE/EA- X A E -robustness. A complete characterization of AE/EA- X A E -robustness and AE/EA- X E A -robustness for a special type of interval matrices, so-called interval circulant matrices, is presented. [ABSTRACT FROM AUTHOR]

This paper addresses the single-machine scheduling with general truncated learning effects (GTLE) and delivery times that are past sequence dependent (DT psd) . The objective is to determine an optimal job schedule such that makespan, sum of the β th power of job completion times, and total weighted completion time are minimized, where β > 0 is a given constant. We proved that the makespan, the sum of the β th power of job completion times, and a special case of the total weighted completion time can be solved in polynomial time. For the general case of the total weighted completion time, we propose the heuristic, simulated annealing and branch-and-bound algorithms. Extensive numerical experiments validate the efficiency of the proposed solution algorithms on a set of randomly generated instances. Furthermore, the computational experiment is also conducted to show that the simulated annealing performs effectively and efficiently. [ABSTRACT FROM AUTHOR]

We study a batch scheduling problem on a two-machine flowshop. Unlike most relevant research papers focusing on batching with identical job processing times, we assume machine-dependent processing times. The objective function is minimum makespan. For the relaxed version of the problem, where integer batch sizes are not required, we introduce a constant time solution. It consists of: (i) a closed-form expression for the optimal number of batches; and (ii) a geometric sequence of the batch sizes. This optimal non-integer solution is converted into an integer solution by the application of a simple rounding procedure, which runs in O(nlogn) time (where n is the number of jobs). [ABSTRACT FROM AUTHOR]

In scheduling with early work, jobs are assigned to a machine by maximizing the parts of non-preemptive jobs executed before their due dates. This paper considers a weighted early work maximization problem on parallel, identical machines with an antithetical property, which holds that w i ≤ w j implies d i ≥ d j for any two jobs i and j where w j and d j are weight and due date of job j, respectively. We show that the problem is weakly NP-hard. Due to the high complexity of dynamic programming, we develop three solution approaches: mixed-integer programming, heuristics, and a branch-and-bound algorithm. Through numerical experiments, we verify their performance. [ABSTRACT FROM AUTHOR]

This paper presents a method by which decision-makers of the Earth observation satellite operations can coordinate pricing and operational decisions. The pricing of satellite images is complex due to uncertainty and high combinatorial complexity in the scheduling, and the high number of evaluation criteria associated with the customers' image requests. Likewise, any price changes will change the final schedule due to the complex scheduling procedure and preference reflected in the scoring, and understanding how is challenging. In addition, the changes can be very scenario-specific, so a change that seems beneficial in one scenario can lead to other outcomes in others. Therefore, this paper poses a method with which the satellite operator through simulation can investigate the robustness and combined effect of preference and pricing in order to select the pricing strategy that emphasizes the chosen preference structure the best while still finding a compromise on conflicting objectives related to profit, quantity, quality, etc. More specifically, the proposed method allows the satellite operators to take advantage of the scheduling flexibility through the decisions they control, i.e., price and preference structure. [ABSTRACT FROM AUTHOR]

We consider the problem of scheduling jobs with equal lengths and arbitrary sizes on uniform parallel batch machines with different capacities. Each machine can only process the jobs whose sizes are not larger than its capacity. Several jobs can be processed as a batch simultaneously on a machine, as long as their total size does not exceed the machine’s capacity. The objective is to minimize makespan. Under a divisibility constraint, we obtain two efficient exact algorithms. For the general problem, we obtain an efficient 2-approximation algorithm. Previous work has shown that the problem cannot be approximated to within an approximation ratio better than 2, unless P = NP, even when all machines have identical speeds and capacities.

Parallel batch scheduling has many applications in the industrial sector, like in material and chemical treatments, mold manufacturing and so on. The number of jobs that can be processed on a machine mostly depends on the shape and size of the jobs and of the machine. This work investigates the problem of batching jobs with multiple sizes and multiple incompatible families. A flow formulation of the problem is exploited to solve it through two column generation-based heuristics. First, the column generation finds the optimal solution of the continuous relaxation, then two heuristics are proposed to move from the continuous to the integer solution of the problem: one is based on the price-and-branch heuristic, the other on a variable rounding procedure. Experiments with several combinations of parameters are provided to show the impact of the number of sizes and families on computation times and quality of solutions. [ABSTRACT FROM AUTHOR]