Explore the vast range of titles available.

Order acceptance and scheduling problem consist of simultaneously deciding which orders to be selected and how to schedule these selected orders. An extension of the sequence-dependent setup times and release dates was introduced in 2010 and a mathematical formulation was presented. Since then, a few mathematical formulations have appeared in the literature by addressing this problem on the basis of sequence-dependent setup times. However, some of the mathematical formulations are nonlinear or lack usability. Therefore, the model presented in 2010 is still being considered in recent studies. In this paper, we investigated the case in which there are sequence-dependent setup times with no release dates for all orders. We developed a new mathematical formulation with O(n2) binary variables and O(n2) constraints. In order to see the performance of our formulation, we conducted a computational analysis with CPLEX 12.4 by solving benchmark instances available in the literature. To manage the comparison, we reduced the existing formulation to the without release dates for all orders. As a result, we observed that the existing formulation can solve the test problems with up to 10 orders in a given time limit. On the other hand, our proposed formulation can solve all the available instances with up to 100 orders within the same time limit. Our proposed formulation is extremely faster than the existing one and can solve small and moderate sized real-life problems in a reasonable time. Thus, the researchers do not need any special heuristics for solving such problems. Instead, they can directly use our formulation with an optimizer.

In this paper, the capacitated lot-sizing and scheduling problem with sequence dependent setup times and costs in a closed loop supply chain is addressed. The system utilizes the closed-loop supply chain strategy so that the multi-class single-level products are produced through both manufacturing of raw materials and remanufacturing of returned recovered products. In this system, a single machine with a limited capacity in each time period is used to perform both the manufacturing and remanufacturing operations. The sequence-dependent setup times and costs (both between two lots of products of different classes and between two lots belonging to the same class of products produced through different methods) are considered. A large-bucket mixed integer programming formulation is proposed for the problem. This model minimizes not only the manufacturing and remanufacturing costs, the setup costs and the inventory holding and backlogging costs over the planning horizon, but also the energy costs paid for the utilization of machine and the compression of processing times. Since the problem is NP-hard, a matheuristic and a grey wolf optimization algorithm are proposed to solve it. To evaluate the efficiency of the proposed algorithm, some experimental instances are generated and solved. The obtained results show the effectiveness of the proposed algorithms.

In this paper we study the classical single machine scheduling problem where the objective is to minimize the weighted number of tardy jobs. Our analysis focuses on the case where one or more of three natural parameters is either constant or is taken as a parameter in the sense of parameterized complexity. These three parameters are the number of different due dates, processing times, and weights in our set of input jobs. We show that the problem belongs to the class of fixed parameter tractable (FPT) problems when combining any two of these three parameters. We also show that the problem is polynomial-time solvable when either one of the latter two parameters are constant, complementing Karp’s result who showed that the problem is NP-hard already for a single due date.

The 1|s-batch(∞),rj|∑wjUj 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(∞),rj|∑wjUj 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(∞),rj|∑wjUj 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(∞),rj|∑wjUj 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.

Sequencing problems are among the most prominent problems studied in operations research, with primary application in, e.g., scheduling and routing. We propose a novel approach to solving generic sequencing problems using multivalued decision diagrams (MDDs). Because an MDD representation may grow exponentially large, we apply MDDs of limited size as a discrete relaxation to the problem. We show that MDDs can be used to represent a wide range of sequencing problems with various side constraints and objective functions, and we demonstrate how MDDs can be added to existing constraint-based scheduling systems. Our computational results indicate that the additional inference obtained by our MDDs can speed up a state-of-the art solver by several orders of magnitude, for a range of different problem classes.

This study examines the problem of minimizing job lateness in the paper manufacturing industry, focusing on cut-size machine scheduling under fluctuating demand. Historical demand data (2018–2019) were forecast using Double Exponential Smoothing (DES) and Holt–Winters’ Triple Exponential Smoothing (TES), with accuracy assessed via Mean Absolute Percentage Error (MAPE). The forecasts informed scheduling models for single- and parallel-machine environments using dispatching rules, including Earliest Due Date (EDD), Shortest Processing Time (SPT), Critical Ratio (CR), Longest Processing Time (LPT), and Least Slack Time (LST). Results show Holt–Winters’ TES achieves the most accurate forecasts, while EDD consistently minimizes lateness, reducing delays by more than 70% compared with alternatives. These findings highlight the value of integrating forecasting and scheduling to enhance machine utilization and delivery performance. The framework offers practical guidance for demand planning and resource allocation in export-oriented manufacturing sectors facing high demand variability.

We consider a non-preemptive single machine scheduling problem for a non-negative penalty function f, where an optimal schedule satisfies the left-shifted property, i.e. in any optimal sequence all executions happen without idle time with a starting time t0≥0. For this problem, every job j has a priority weight wj and a processing time pj, and the goal is to find an order on the given jobs that minimizes ∑wjf(Cj), where Cj is the completion time of job j. This paper explores local dominance properties, which provide a powerful theoretical tool to better describe the structure of optimal solutions by identifying rules that at least one optimal solution must satisfy. We propose a novel approach, which allows to prove that the number of sequences that respect the local dominance property among three jobs is only two, not three, reducing the search space from n! to n!/3⌈n/3⌉ schedules. In addition, we define some non-trivial cases for the problem with a strictly convex penalty function that admits an optimal schedule, where the jobs are ordered in non-increasing weight. Finally, we provide some insights into three future research directions based on our results (i) to reduce the number of steps required by an exact exponential algorithm to solve the problem, (ii) to incorporate the dominance properties as valid inequalities in a mathematical formulation to speed up implicit enumeration methods, and (iii) to show the computational complexity of the problem of minimizing the sum of weighted mean squared deviation of the completion times with respect to a common due date for jobs with arbitrary weights, whose status is still open.

The problem of sequencing and scheduling airplanes landing and taking off on a runway is a major challenge for air traffic management. This difficult real-time task is still carried out by human controllers, with little help from automatic tools. Several methods have been proposed in the literature, including mixed-integer programming (MIP)–based approaches. However, there is an opinion that MIP is unattractive for real-time applications, since computation times are likely to grow too large. In this paper, we reverse this claim, by developing a MIP approach able to solve to optimality real-life instances from congested airports in the stringent times allowed by the application. To achieve this, it was mandatory to identify new classes of strong valid inequalities, along with developing effective fixing and lifting procedures.

In this paper, we consider single-machine scheduling with multiple due dates per job. This is motivated by several industrial applications, where it is not important by how much we miss a due date. Instead the relevant objective is to minimize the number of missed due dates. Typically, this situation emerges whenever fixed delivery appointments are chosen in advance, such as in the production of individualized pharmaceuticals or when customers can only receive goods at certain days in the week, due to constraints in their warehouse operation. We compare this previously unexplored problem with classical due date scheduling, for which it is a generalization. We show that single-machine scheduling with multiple due dates is NP-hard in the strong sense if processing times are job dependent. If processing times are equal for all jobs, then single-machine scheduling with multiple due dates is at least as hard as the long-standing open problem of weighted tardiness with equal processing times and release dates 1∣rj,pj=p∣∑wjTj. Finally, we focus on the case of equal processing times and provide several polynomially solvable special cases as well as an exact branch-and-bound algorithm and heuristics for the general case. Experiments show that our branch-and-bound algorithm compares well to modern exact methods to solve problem 1∣rj,pj=p∣∑wjTj.

In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be NP-hard, while also proving NP-hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task setting.