Single Machine Scheduling

In this paper, the problem of scheduling n jobs on a single machine is evaluated. We introduce a Modified Total Late Work function that allows a declining piecewise linear penalty over time. Multiple due dates for each job are identified and at each due date, the penalty is reassessed. Many instances occur when delivery urgency leads to progress metrics or dates being added to a contract. Over the life of the contract, a loss of incentives or a price decrease can occur at each of the negotiated due dates. After the final due date, the product is valueless and the penalty ceases to accrue. The number and placement of contract due dates are part of the initial negotiations. Two metaheuristics, Simulated Annealing and the Noising Method, are empirically evaluated to determine their performance when measured by this new loss function.

• A submitted manuscript is the author's version of the article upon submission and before peer-review. There can be important differences between the submitted version and the official published version of record. People interested in the research are advised to contact the author for the final version of the publication, or visit the DOI to the publisher's website. • The final author version and the galley proof are versions of the publication after peer review. • The final published version features the final layout of the paper including the volume, issue and page numbers.

This paper starts by studying the performance of two inte"elated genetic algorithms (GA) for the static Single Machine Scheduling Problem (SMSP). One Is a single start GA, the other, called MetaGA, is a multi-start version GA. The performance is evaluated, for total weighted tardiness, on the basis of the quality of scheduling solutions obtained for a limit on computation time. Then, a scheduling system, based on Genetic Algorithms is proposed, for the resolution of the dynamic version of the same problem. The approach used adapts the resolution of the static problem to the dynamic one in which changes may occur continually. This takes into account dynamic occu"ences in a system and adapts the cu"ent population to a new regenerated population,

The study deals with scheduling a set of independent jobs with unequal release dates to minimize total weighted tardiness on a single machine. We propose new dominance properties that are incorporated in a branch and bound algorithm. The proposed algorithm is tested on a set of randomly generated problems with 10, 15 and 20 jobs. To the best of our knowledge, this is the first exact approach that attempts to solve the 1jr j j P w j T j problem.

The following case of the classical NP-hard scheduling problem is considered. There is a set of jobs N with identical processing times p = const. All jobs have to be processed on a single machine. The objective function is minimization of maximum lateness. We analyze algorithms for the makespan problem, presented by and and represent two polynomial algorithms to solve the problem and to construct the Pareto set with respect to criteria L max and C max . The complexity of presented algorithms equals O(Q • n log n) and O(n 2 log n), where 10 -Q is the accuracy of the input-output parameters.

In this paper, the single-track railway scheduling problem with two stations and several segments of the track is considered. Two subsets of trains are given, where trains from the first subset go from the first station to the second station, and trains from the second subset go in the opposite direction. The speed of trains over each segment is the same. A polynomial time reduction from the problem under consideration to a special case of the single-machine equal-processing-time scheduling problem with setup times is presented. Different polynomial time algorithms are developed for special cases with divers objective functions under various constraints. Moreover, several theoretical results which can be ranked in a series of similar investigations of NP-hardness of equal-processing-time single-machine scheduling problems without precedence relations are obtained.

We study the classical NP-hard in the ordinary sense singlemachine total tardiness scheduling problem 1 | | Tj. New polynomial and pseudo-polynomial solvable cases of the problem are presented and respective algorithms are proposed with no more than O(n 2 pj) time.

We propose a hybrid algorithm based on the Ant Colony Optimization (ACO) meta-heuristic, in conjunction with four well-known elimination rules, to tackle the N P -hard single-machine scheduling problem to minimize the total job tardiness. The hybrid algorithm has the same running time as that of ACO. We conducted extensive computational experiments to test the performance of the hybrid algorithm and ACO. The computational results show that the hybrid algorithm can produce optimal or near-optimal solutions quickly, and its performance compares favourably with that of ACO for handling standard instances of the problem.

An uncertain single-machine scheduling problem is considered, where the processing time of a job can take any real value from a given segment. The criterion is to minimize the total weighted completion time of the n jobs, a weight being associated with each given job. We use the optimality box as a stability measure of the optimal schedule and derive an O(n)-algorithm for calculating the optimality box for a fixed permutation of the given jobs. We investigate properties of the optimality box using blocks of the jobs. If each job belongs to a single block, then the largest optimality box may be constructed in O(n log n) time. For the general case, we apply dynamic programming for constructing a job permutation with the largest optimality box. The computational results for finding a permutation with the largest optimality box show that such a permutation is close to an optimal one, which can be determined after completing the jobs when their processing times became known.

We consider a single-machine scheduling problem with each job having an uncertain processing time which can take any real value within each corresponding closed interval before completing the job. The scheduling objective is to minimize the total weighted flow time of all n jobs, where there is a weight associated with each job. We establish the necessary and sufficient condition for the existence of a job permutation which remains optimal for any possible realizations of these n uncertain processing times. We also establish the necessary and sufficient condition for another extreme case that for each of the n! job permutations there exists a possible realization of the uncertain processing times that this permutation is uniquely optimal. Testing each of the conditions takes polynomial time in terms of the number n of jobs. We develop precedence-dominance relations among the n jobs in dealing with the general case of this uncertain scheduling problem. In case there exist no precedence-dominance relations among a subset of n jobs, a heuristic procedure to minimize the maximal absolute or relative regret is used for sequencing such a job subset. Computational experiments for randomly generated instances with n jobs (5 ≤ n ≤ 1000) show that the established precedence-dominance relations are quite useful in reducing the total weighted flow time.

We consider a single-machine scheduling problem, in which the processing time of a job can take any value from a given segment. The criterion is to minimize the sum of weighted completion times of the n jobs, a weight being associated with a job. For a job permutation, we study the stability box, which is a subset of the stability region. We derive an O(n log n) algorithm for constructing a job permutation with the largest dimension and volume of a stability box. The efficiency of a permutation with the largest dimension and volume of a stability box is demonstrated via a simulation on a set of randomly generated instances.

This paper describes a robust approach for the single machine scheduling problem 1|r i |L max . The method is said robust since it characterizes a large set of optimal solutions allowing to switch from one solution to another, without any performance loss, in order to face the potential disruptions which occur during the schedule execution. It is based on a dominance theorem that characterizes a set of dominant sequences, using the interval structure defined by the relative order of the release and the due dates of the jobs. The performance of a set of dominant sequences can be determined in polynomial time by computing the most favorable and the most unfavorable sequences associated with each job, with regard to the lateness criterion. A branch and bound procedure is proposed which modifies the interval structure of the problem in order to tighten the dominant set of sequences so that only the optimal sequences are conserved.

In this paper, we investigate the single machine scheduling problem with release dates and tails and a planned unavailability time period. We show that the problem admits a fully polynomial-time approximation scheme when the tails are equal. We derive an approximation algorithm for the general case and we show that the worst-case bound of the sequence yielded by Schrage's algorithm is equal to 2 and that this bound is tight. Some consequences of this result are also presented.

Abstract¾In this paper, we present particle swarm optimization (PSO) and differential evolution (DE) algorithms for the job shop scheduling problem with the makespan criterion. The applications of PSO and DE on combinatorial optimization problems are still considered limited, but the advantages of PSO and DE algorithms such as structural simplicity, accessibility to practical applications, ease of implementation, speed to get the solutions, and robustness are already shown in the literature. However, the major obstacle of successfully applying PSO and DE algorithms to combinatorial optimization problems is due to their continuous nature. To remedy this drawback, the smallest position value (SPV) rule presented in Tasgetiren et al.(2004a, b, c, d) is employed in both algorithms to convert continuous position values to discrete job permutations. In order to improve the solution quality, both algorithms are also hybridized with an efficient local search method based on a variable neighborhood search (VNS) technique. The experimental results based on the well known benchmark instances collected from OR library show that the hybrid PSO algorithm has generated slightly better results than its counterpart, namely, the DE algorithm. It is also shown that the hybrid PSO algorithm is either better or competitive to the state-of-the-art methods in the literature. In addition, to the best of our knowledge, both algorithms are the first reported applications of PSO and DE algorithms for the job shop scheduling problem in the literature.

In this paper, we have improved solutions for two of the Multi-Criteria Machine Scheduling Problems (MCMSP). These problems are to maximize early jobs time and range of lateness jobs times 1//(𝐸 𝑚𝑎𝑥 , 𝑅 𝐿 )), and the second problem is maximum tardy jobs time and range of lateness jobs times 1//(𝑇 𝑚𝑎𝑥 , 𝑅 𝐿 ) in a single machine with Multi-Objective Machine Scheduling Problems (MOMSP) 1//(𝐸 𝑚𝑎𝑥 , 𝑅 𝐿 )and 1//(𝑇 𝑚𝑎𝑥 , 𝑅 𝐿 ) which are derived from the main problems respectively. The Local Search Methods (LSMs), Bees Algorithm (BA), and a Simulated Annealing (SA) are applied to solve all suggested problems. Finally, the experimental results of the LSMs are compared with the results of the Branch and Bound (BAB) method for a reasonable time. These results are ensuring the efficiency of LSMs.

The existing Modified Hungarian Method for solving the unbalanced assignment problem used multiple jobs assigning process but not used limit of assigned jobs to a single machine, when multiple jobs assign to a single machine then problem occurs that how many jobs can be assigned to a single machine. To overcome this problem, we introduce time parameter on each machine. The present algorithm is implemented on numerical example for better understanding and also coded in Python 3.9.0 programming language.

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 the latter two parameters are constant, complementing Karp's result who showed that the problem is NP-hard already for a single due date.

This paper is concerned with the 1|| pjUj problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental scheduling problem, but also a very important problem from a theoretical point of view as it generalizes the Subset Sum problem and is closely related to the 0/1-Knapsack problem. The problem is well-known to be NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time algorithms. The fastest known pseudo-polynomial time algorithm for the problem is the famous Lawler and Moore algorithm which runs in O(P • n) time, where P is the total processing time of all n jobs in the input. This algorithm has been developed in the late 60s, and has yet to be improved to date. In this paper we develop two new algorithms for 1|| pjUj , each improving on Lawler and Moore's algorithm in a different scenario: -Our first algorithm runs in Õ(P 7/4 ) time 1 , and outperforms Lawler and Moore's algorithm in instances where n = ω(P 3/4 ). -Our second algorithm runs in Õ(min{P • D # , P + D}) time, where D # is the number of different due dates in the instance, and D is the sum of all different due dates. This algorithm improves on Lawler and Moore's algorithm when n = ω(D # ) or n = ω(D/P ). Further, it extends the known Õ(P ) algorithm for the single due date special case of 1|| pjUj in a natural way. Both algorithms rely on basic primitive operations between sets of integers and vectors of integers for the speedup in their running times. The second algorithm relies on fast polynomial multiplication as its main engine, while for the first algorithm we define a new "skewed" version of (max, min)-convolution which is interesting in its own right. ⋆ This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979). 1 Throughout the paper we use Õ(•) to suppress logarithmic factors.

This paper is concerned with the 1|| pjUj problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental scheduling problem, but also a very important problem from a theoretical point of view as it generalizes the Subset Sum problem and is closely related to the 0/1-Knapsack problem. The problem is well-known to be NP-hard, but only in a weak sense, meaning it admits pseudo-polynomial time algorithms. The fastest known pseudo-polynomial time algorithm for the problem is the famous Lawler and Moore algorithm which runs in O(P • n) time, where P is the total processing time of all n jobs in the input. This algorithm has been developed in the late 60s, and has yet to be improved to date. In this paper we develop two new algorithms for 1|| pjUj, each improving on Lawler and Moore's algorithm in a different scenario: Our first algorithm runs in Õ(P 7/4 ) time 1 , and outperforms Lawler and Moore's algorithm in instances where n = ω(P 3/4 ). Our second algorithm runs in Õ(min{P • D # , P + D}) time, where D # is the number of different due dates in the instance, and D is the sum of all different due dates. This algorithm improves on Lawler and Moore's algorithm when n = ω(D # ) or n = ω(D/P ). Further, it extends the known Õ(P ) algorithm for the single due date special case of 1|| pjUj in a natural way. Both algorithms rely on basic primitive operations between sets of integers and vectors of integers for the speedup in their running times. The second algorithm relies on fast polynomial multiplication as its main engine, while for the first algorithm we define a new "skewed" version of (max, min)convolution which is interesting in its own right. Keywords and phrases Weighted number of tardy jobs, sumsets, convolutions 1 Throughout the paper we use Õ(•) to suppress logarithmic factors.

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 the latter two parameters are constant, complementing Karp's result who showed that the problem is NP-hard already for a single due date.

This paper deals with a common due date parallel machines scheduling problem in which each job has a different tardiness penalty. The objective is to minimize the total weighted tardiness. The scheduling problem of minimizing the total weighted tardiness with a common due date on a single machine is known to be ordinary NP-hard. This is also the case for

In this paper, we consider scheduling problems on a single machine in a sequence dependent setup environment. For these problems, we introduce several integer programming formulations of varying size and strength. Computational experiments conducted on instances of 1|s ij | C j (i.e. minimizing total flow time on a single machine under sequence dependent setup times) and 1|s ij | T j (i.e. minimizing total tardiness on a single machine under sequence dependent setup times) illustrate the benefits of using stronger formulations, even though the computation of their LP relaxation is more time consuming. Incorporating these improved LP relaxation bounds, we propose an exact branch-and-bound algorithm able to solve instances of 1|s ij | C j and 1|s ij | T j having up to 50 and 45 jobs respectively.

The multi-criteria problem of scheduling n jobs on a single machine was considered in this paper. The criteria belong to minimize total completion times, total tardiness and total late work and minimize total completion times, total tardiness and maximum late work by using some exact and local search methods. The proposed methods for solving these minimization problems were seemed to be helpful in finding the set of all efficient solutions. This set of all efficient solutions is not easy to find, therefore, it could be preferable to have an approximation to that set in a reasonable amount of time. Therefore branch and bound (BAB) technique was proposed as an exact approach, while the Genetic algorithm (GA) and Particle Swarm Optimization (PSO) methods were also proposed as local search methods. Keywords : Multiple objective Scheduling, Branch and Bound, Pareto Optimal Solutions, Genetic Algorithm, Particle Swarm Optimization.

This article addresses the no-wait flowshop scheduling problem with simultaneous consideration of common due date assignment, convex resource allocation and learning effect in a two machine setting. The processing time of each job can be controlled by its position in a sequence and also by allocating extra resource, which is a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the optimal common due date, the resource allocation and the schedule of jobs such that the total earliness, tardiness and common due date cost (the total resource consumption cost) are minimized under the constraint condition that the total resource consumption cost (the total earliness, tardiness and common due date cost) is limited. Polynomial time algorithms are developed for two versions of the problem.

This article addresses the no-wait flowshop scheduling problem with simultaneous consideration of common due date assignment, convex resource allocation and learning effect in a two machine setting. The processing time of each job can be controlled by its position in a sequence and also by allocating extra resource, which is a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the optimal common due date, the resource allocation and the schedule of jobs such that the total earliness, tardiness and common due date cost (the total resource consumption cost) are minimized under the constraint condition that the total resource consumption cost (the total earliness, tardiness and common due date cost) is limited. Polynomial time algorithms are developed for two versions of the problem.

Thts paper considers the problem of minimizing the weighted sum ofearhness and tardiness penalues on a single machine A simple and efficient lower bound is developed and several upper bounds are proposed A branch and bound procedure incorporating the bounds, precedence relatmns and dominance properties ~s proposed An experiment is designed to test the efficiency of the bounds, precedence relatmns, etc Com,~atatmnal experience w~lh problems up to 20 jobs Is reported

This article examines the single-machine scheduling problem to minimize total flow time with unequal release dates. This problem has been proven to be NP-hard. We present a necessary and sufficient condition for local optimality which can also be considered as a priority rule. On the basis of this condition, we then define a class of schedules which contains all optimal solutions. We present some efficient heuristic algorithms using the previous condition to build a schedule belonging to this subset. We also prove some new dominance theorems. discuss the results found in the literature for this problem, and propose a branch-and-bound algorithm in which the heuristics are used to provide good upper bounds. We compare this new algorithm with existing algorithms found in the literature. Computational results on problems with up to 100 jobs indicate that the proposed branch-and-bound algorithm is superior to previously published algorithms. I: 1992 John Wile! & Sons. S such that F ( S ) = C ; l = , F,(S) is minimal. This problem is equivalent to the problem of minimizing the total job lateness, total completion time. total waiting time, and mean number of jobs in the shop (Conway. Maxwell, and Miller [6]). In the case of equal release dates. this problem can easily be solved by applying the SPT (shortest processing time) priority rule (Smith [13]). The SPT priority rule consists of scheduling a job with the shortest processing time among the unscheduled jobs each time the machine becomes idle.

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem at once. In particular, we have n clients over a period of m days, where each client has a single job with its own processing time and deadline per day. Our goal is to provide a schedule for each of the m days, so that each client is guaranteed to have their job meet its deadline in at least k

In this paper, we consider the single-machine scheduling problem with given release dates and the objective to minimize the maximum penalty which is NP-hard in the strong sense. For this problem, we introduce a dual and an inverse problem and show that both these problems can be solved in polynomial time. Since the dual problem gives a lower bound on the optimal objective function value of the original problem, we use the optimal function value of a sub-problem of the dual problem in a branch and bound algorithm for the original single-machine scheduling problem. We present some initial computational results for instances with up to 20 jobs.

In this paper, a generalized formulation of a classical single machine scheduling problem is considered. A set of n jobs characterized by their release dates, deadlines and a start time-dependent processing time function p(t) has to be processed on a single machine. The objective is to find a Pareto-optimal set of schedules with respect to the criteria ϕ max and makespan, where ϕ max is a non-decreasing function depending on the completion times of the jobs. We present an approach that allows to find an optimal schedule with respect to different scheduling criteria, such as the minimization of makespan, lateness or weighted lateness, tardiness and weighted tardiness etc. in time polynomially depending on the number of jobs. The complexity of the presented algorithm is O(n 3 max{log n, H, P }), where H and P are the complexity of calculating ϕ j (t) and p(t), respectively.

In this paper, we present a modification of dynamic programming algorithms (DPA), which we denote as graphical algorithms (GrA). For the knapsack problem and some single machine scheduling problems, it is shown that the time complexity of the GrA is less than the time complexity of the standard DPA. Moreover, the average running time of the GrA is often essentially smaller. A GrA can also solve largescale instances and instances, where the parameters are not integer. In addition, for some problems, GrA has a polynomial time complexity in contrast to a pseudo-polynomial complexity of DPA.

In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness 1|| max T j and for the problem of maximizing the number of tardy jobs 1|| max U j . In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem 1|| max U j is polynomially solvable. For several special cases of problem 1|| max T j , we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.