Scheduling problems with a common due window assignment: A survey
---
paper_title: COMMON DUE-WINDOW SCHEDULING

paper_content:

In this paper, we solve common due-window scheduling problems within the just-in-time window concept, i.e., scheduling problems including both earliness and tardiness penalties. We assume that jobs share the same due window and incur no penalty as long as they are completed within the due window. We further assume that the earliness and tardiness penalty factors are constant and that the size of the window is a given parameter. ::: ::: ::: ::: For cases where the location of the due window is a decision variable, we provide a polynomial algorithm with complexity O(n * log (n)) to solve the problem. For cases where the location of the due window is a given parameter, we use dynamic programming with pseudopolynomial complexity to solve the problem.
---
paper_title: Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids

paper_content:

Tasks scheduling and resource allocation are among crucial issues in any large scale distributed system, including Computational Grids (CGs). These issues are commonly investigated using traditional computational models and resolution methods that yield near-optimal scheduling strategies. One drawback of such approaches is that they cannot effectively tackle the complex nature of CGs. On the one hand, such systems account for many administrative domains with their own access policies, user privileges, etc. On the other, CGs have hierarchical nature and therefore any computational model should be able to effectively express the hierarchical architecture in the optimization model. Recently, researchers have been investigating the use of game theory for modeling user requirements regarding task and resource allocation in grid scheduling problems. In this paper we present two general non-cooperative game approaches, namely, the symmetric non-zero sum game and the asymmetric Stackelberg game for modeling grid user behavior defined as user requirements. In our game-theoretic approaches we are able to cast new requirements arising in allocation problems, such as asymmetric users relations, security and reliability restrictions in CGs. For solving the games, we designed and implemented GA-based hybrid schedulers for approximating the equilibrium points for both games. The proposed hybrid resolution methods are experimentally evaluated through the grid simulator under heterogeneity, and large-scale and dynamics conditions. The relative performance of the schedulers is measured in terms of the makespan and flowtime metrics. The experimental analysis showed high efficiency of meta-heuristics in solving the game-based models, especially in the case of an additional cost of secure task scheduling to be paid by the users.
---
paper_title: COMMON DUE-WINDOW SCHEDULING

paper_content:

In this paper, we solve common due-window scheduling problems within the just-in-time window concept, i.e., scheduling problems including both earliness and tardiness penalties. We assume that jobs share the same due window and incur no penalty as long as they are completed within the due window. We further assume that the earliness and tardiness penalty factors are constant and that the size of the window is a given parameter. ::: ::: ::: ::: For cases where the location of the due window is a decision variable, we provide a polynomial algorithm with complexity O(n * log (n)) to solve the problem. For cases where the location of the due window is a given parameter, we use dynamic programming with pseudopolynomial complexity to solve the problem.
---
paper_title: Single-machine scheduling with time windows and earliness/tardiness penalties

paper_content:

Abstract We study the single machine earliness/tardiness problem with arbitrary time windows (STW). We show that STW is NP-hard and then decompose it into the subproblems of finding a good job sequence and optimally inserting idle time into a given sequence. We propose heuristics for the sequencing subproblem by appropriately modifying heuristics originally developed for other single machine scheduling problems. Experimentation with randomly generated problems shows that one of the proposed heuristics is computationally efficient and capable of finding good solutions to problems of arbitrary size. We also propose an algorithm to optimally insert idle time into a given job sequence.
---
paper_title: A production scheduling strategy with a common due window

paper_content:

This paper studies a production scheduling problem in a multinational company in Hong Kong, the headquarters, sales branches and factories of which are located in different countries and regions. Some orders are required to go for processing in a particular factory. Based on a Just-In-Time (JIT) strategy, an objective function is defined for the production scheduling problem with a due window. A series of Lemmas and a polynomial-time algorithm are presented to determine the optimal due window and sequence. The algorithm is tested on data collected from the company. Computational results demonstrate the effectiveness of the algorithm.
---
paper_title: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

paper_content:

The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography.
---
paper_title: Minmax scheduling problems with a common due-window

paper_content:

This paper focuses on a minmax due-window assignment problem. The goal is to schedule the jobs and the due-window such that the highest cost among all jobs is minimized. The objective function contains four cost components: for earliness, tardiness, due-window starting time and due-window size. We present a polynomial time solution for the case of a single machine and for a two-machine flow-shop. The cases of parallel identical machines and uniform machines are NP-hard, and simple heuristics and lower bounds are introduced and tested numerically. Scope and purpose Contracts between suppliers and customers often contain a time interval (a due-window), such that goods delivered within this interval are considered to be on time and are not penalized. The due-window starting time and size are determined during sales negotiations with customers. A late and/or large due-window clearly makes the supplier less attractive, and hence the total cost function should increase in the due-window starting time and size. This paper focuses on due-window assignment problems on several classical machine settings: a single machine, a two-machine flow-shop and parallel identical and uniform machines.
---
paper_title: Due‐window assignment with unit processing‐time jobs

paper_content:

In due-window assignment problems, jobs completed within a designated time interval are regarded as being on time, whereas early and tardy jobs are penalized. The objective is to determine the location and size of the due-window, as well as the job schedule. We address a common due-window assignment problem on parallel identical machines with unit processing time jobs. We show that the number of candidate values for the optimal due-window starting time and for the optimal due-window completion time are bounded by 2. We also prove that the starting time of the first job on each of the machines is either 0 or 1, thus introducing a fairly simple, constant-time solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004
---
paper_title: Soft Due Window Assignment and Scheduling on Parallel Machines

paper_content:

We study problems of scheduling jobs on identical parallel machines, in which a due window has to be assigned to each job. If a job is completed within its due window, then it incurs no scheduling cost. Otherwise, it incurs earliness or tardiness cost. Two due window models are considered. In both models, the due window size is a decision variable common for all jobs. In the first model, called a constant due window, the due window starting time is a decision variable common for all jobs, and in the second, called a slack due window, the due window starting time is equal to the job processing time plus a decision variable common for all jobs. The objective is to find a job schedule as well as the size and location(s) of the due window(s) such that a weighted maximum or sum of costs associated with job earliness, job tardiness, and due window size is minimized. We establish the properties of optimal solutions of these minmax and minsum problems. For a constant due window model, we prove that the minmax problem with arbitrary weights and the minsum problem with equal weights are polynomially equivalent to the classical parallel machine scheduling problem to minimize the makespan. We further show that the problems for a constant due window model and slack due window model with the same objective function are reversible in the sense that their optimal solutions are mirror images of each other. These results imply O(n) and O(n log n) time algorithms for the considered problems when m=1.
---
paper_title: COMMON DUE-WINDOW SCHEDULING

paper_content:

In this paper, we solve common due-window scheduling problems within the just-in-time window concept, i.e., scheduling problems including both earliness and tardiness penalties. We assume that jobs share the same due window and incur no penalty as long as they are completed within the due window. We further assume that the earliness and tardiness penalty factors are constant and that the size of the window is a given parameter. ::: ::: ::: ::: For cases where the location of the due window is a decision variable, we provide a polynomial algorithm with complexity O(n * log (n)) to solve the problem. For cases where the location of the due window is a given parameter, we use dynamic programming with pseudopolynomial complexity to solve the problem.
---
paper_title: A due-window assignment problem with position-dependent processing times

paper_content:

We extend a classical single-machine due-window assignment problem to the case of position-dependent processing times. In addition to the standard job scheduling decisions, one has to assign a time interval (due-window), such that jobs completed within this interval are assumed to be on time and not penalized. The cost components are: total earliness, total tardiness and due-window location and size. We introduce an O(n3) solution algorithm, where n is the number of jobs. We also investigate several special cases, and examine numerically the sensitivity of the solution (schedule and due-window) to the different cost parameters.
---
paper_title: Common due window size and location determination in a single machine scheduling problem

paper_content:

We consider a single machine static and deterministic scheduling problem in which jobs have a common due window. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The objective is to find the optimal size and location of the window as well as an optimal sequence to minimise a cost function based on earliness, tardiness, window size, and window location. We propose an O(n log n) algorithm to solve the problem.
---
paper_title: Scheduling Problems with Optimal Due Interval Assignment Subject to Some Generalized Criteria

paper_content:

The paper deals with two problems of scheduling jobs on identical parallel machines, in which a due interval should be assigned to each job. Due interval is a generalization of well known classical due date and describes a time interval, in which a job should be finished. In the first problem, we have to find a schedule of jobs and a common due interval such that the sum of the total tardiness, the total earliness and due interval parameters is minimized. The second problem is to find a schedule of jobs and an assignment of due interval to all jobs, which minimize the maximum of the following three parts: the maximum tardiness, the maximum earliness and the due int erval parameters. We proved that the considered problems are NP-hard and outlined some methods how to solve them approximately as well as optimally.
---
paper_title: Single processor scheduling problems with various models of a due window assignment

paper_content:

In the paper we investigate four single processor scheduling problems, which deal with the process of the negotiation between a producer and a customer about delivery time of final products. This process is modeled by a due window, which is a generalization of well known classical due date and describes a time interval, in which a job should be finished. Due window assignment is a new approach, which has been investigated in the scientific literature for a few years. In this paper we consider various models of due window assignment. To solve the formulated problems we have to find such a schedule of jobs and such an assignment of due windows to each job, which minimizes a given criterion dependent on the maximum or total earliness and tardiness of jobs and due window parameters. One of the main results is the mirror image of the solutions of the considered problems and other problems presented in the scientific literature. The wide survey of the literature is also given.
---
paper_title: COMMON DUE-WINDOW SCHEDULING

paper_content:

In this paper, we solve common due-window scheduling problems within the just-in-time window concept, i.e., scheduling problems including both earliness and tardiness penalties. We assume that jobs share the same due window and incur no penalty as long as they are completed within the due window. We further assume that the earliness and tardiness penalty factors are constant and that the size of the window is a given parameter. ::: ::: ::: ::: For cases where the location of the due window is a decision variable, we provide a polynomial algorithm with complexity O(n * log (n)) to solve the problem. For cases where the location of the due window is a given parameter, we use dynamic programming with pseudopolynomial complexity to solve the problem.
---
paper_title: Scheduling about an unrestricted common due window with arbitrary earliness/tardiness penalty rates

paper_content:

We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due window to minimize total weighted earliness and tardiness cost. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. Earliness or tardiness cost is assessed when a job completes outside the due window, which may be an instant in time or a time increment defining acceptable job completion. In this paper we present properties that characterize the structure of an optimal schedule, present a lower bound, propose a two-step branch and bound algorithm, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for medium-sized problem instances.
---
paper_title: Earliness-tardiness scheduling problems with a common delivery window

paper_content:

This paper deals with the scheduling of n jobs on a single machine to minimize the sum of weighted earliness and weighted number of tardy jobs given a delivery window. Penalties are not incurred if jobs are completed within the delivery window. The length of this delivery window (which corresponds to the time period within which the customer is willing to take deliveries) is a given constant. We consider two cases of the problem; one where the position of the delivery parameter (restricted window case). We present some optimal properties, prove that the problem (even for the unrestricted window case) is NP-complete, and present dynamic programming algorithms for both cases.
---
paper_title: Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date

paper_content:

This paper and its companion Part II concern the scheduling of jobs with cost penalties for both early and late completion. In Part I, we consider the problem of minimizing the weighted sum of earliness and tardiness of jobs scheduled on a single processor around a common due date, d. We assume that d is not early enough to constrain the scheduling decision. The weight of a job does not depend on whether the job is early or late, but weights may vary between jobs. We prove that the recognition version of this problem is NP-complete in the ordinary sense. We describe optimality conditions, and present a computationally efficient dynamic programming algorithm. When the weights are bounded by a polynomial function of the number of jobs, a fully polynomial approximation scheme is given. We also describe four special cases for which the problem is polynomially solvable. Part II provides similar results for the unweighted version of this problem, where d is arbitrary.
---
paper_title: A note: a due-window assignment problem on parallel identical machines

paper_content:

We solve a due-window assignment problem on parallel identical machines. In addition to the standard objective of finding the optimal job schedule, in due-window assignment problems one has to assign a time interval during which goods are delivered to customers with no cost. Jobs scheduled prior to or after the due-window are penalized according to their earliness/tardiness value. We assume that jobs have identical processing times, but may have job-dependent earliness and tardiness costs (eg, due to possible different destinations). We show that the problem can be reduced to a non-standard asymmetric assignment problem, and introduce an efficient (O(n4)) solution procedure.
---
paper_title: Scheduling with a common due-window: Polynomially solvable cases

paper_content:

The single machine scheduling problem to minimize maximum weighted absolute deviations of job completion times from a common due-date, is known to be NP-hard. However, two special cases have been shown to have polynomial time solutions: the case of unit processing time jobs, and the case of due-date assignment for a given job sequence. We extend both cases to a setting of a common due-window. We show that the unit-job problem includes 12 different sub-cases, depending on the size and location of the (given) due-window. Scheduling and due-window assignment for a given job sequence is solved for a single machine, for parallel identical machines and for flow-shops. For each of the above cases, an appropriate special-structured linear program is presented.
---
paper_title: A single machine scheduling problem with common due window and controllable processing times

paper_content:

A static deterministic single machine scheduling problem with a common due window is considered. Job processing times are controllable to the extent that they can be reduced, up to a certain limit, at a cost proportional to the reduction. The window location and size, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the window location, its size, processing time reduction as well as job earliness and tardiness. We show that the problem can be formulated as an assignment problem and thus can be solved with well-known algorithms.
---
paper_title: Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs

paper_content:

Abstract We consider a single machine scheduling problem in which the machine experiences the effects of learning of fatigue as it continues to work and the jobs have due dates and are subject to penalties if they are not completed on time. Because of the effects of learning or fatigue, the performance rate of the machine varies over time. As a result, the processing time of a job depends on its work content as well as the total work content of the jobs completed prior to its loading. In this paper, we prove that even when the machine works at a variable rate, the pair-wise interchange of jobs minimizes the maximum tardiness and a simple modification to the well-known Moore-Hodgson's algorithm yields the minimum number of tardy jobs. Further, we formulate the problem of minimizing the total penalty for tardy jobs as a 0–1 knapsack problem with nested constraints, and solve it by using dynamic programming recursion as well as the maximum-weighted network path algorithm. Then we combine these two techniques and solve the 0–1 knapsack problem, by inducing a nested constraint structure and constructing a network with fewer nodes.
---
paper_title: Minimizing Flow Time on Parallel Identical Processors with Variable Unit Processing Time

paper_content:

We show that minimizing total flow time on parallel identical processors with nonincreasing unit processing time is achieved with shortest processing time SPT scheduling: Sequence the tasks in an order of nondecreasing lengths. Following this order and starting with the shortest task, process any task by the first processor that becomes available. If the unit processing time is allowed to be increasing, e.g., quadratically, the problem becomes NP-hard.
---
paper_title: Scheduling a maintenance activity and due-window assignment on a single machine

paper_content:

We study a single machine scheduling and due-window assignment problem. In addition to the traditional decisions regarding sequencing the jobs and scheduling the due-window, we allow an option for performing a maintenance activity. This activity requires a fixed time interval during which the machine is turned off and no production is performed. On the other hand, after the maintenance time, the machine becomes more efficient, as reflected in the new shortened job processing times. The objective is to schedule the jobs, the due-window and the maintenance activity, so as to minimize the total cost consisting of earliness, tardiness, and due-window starting time and size. We introduce an efficient (polynomial time) solution for this problem.
---
paper_title: Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity

paper_content:

Due-window assignment and production scheduling are important issues in operations management. In this study we investigate the problem of common due-window assignment and scheduling of deteriorating jobs and a maintenance activity simultaneously on a single-machine. We assume that the maintenance duration depends on its starting time. We provide polynomial time solutions for the problem and some of its special cases, where the objective is to simultaneously minimize the earliness, tardiness, due-window starting time, and due-window size costs.
---
paper_title: A bi-criteria two-machine flowshop scheduling problem with a learning effect

paper_content:

This paper addresses a bi-criteria two-machine flowshop scheduling problem when the learning effect is present. The objective is to find a sequence that minimizes a weighted sum of the total completion time and the maximum tardiness. In this article, a branch-and-bound method, incorporating several dominance properties and a lower bound, is presented to search for the exact solution for small job-size problems. In addition, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm for large job-size problems. Finally, computational results for this problem are provided to evaluate the performance of the proposed algorithms.
---
paper_title: Flow-shop scheduling with a learning effect

paper_content:

The paper is devoted to some flow-shop scheduling problems with a learning effect. The objective is to minimize one of the two regular performance criteria, namely, makespan and total flowtime. A heuristic algorithm with worst-case bound m for each criteria is given, where m is the number of machines. Furthermore, a polynomial algorithm is proposed for both of the special cases: identical processing time on each machine and an increasing series of dominating machines. An example is also constructed to show that the classical Johnson's rule is not the optimal solution for the two-machine flow-shop scheduling to minimize makespan with a learning effect. Some extensions of the problem are also shown.
---
paper_title: Single-machine scheduling with learning considerations

paper_content:

The focus of this work is to analyze learning in single-machine scheduling problems. It is surprising that the well-known learning effect has never been considered in connection with scheduling problems. It is shown in this paper that even with the introduction of learning to job processing times two important types of single-machine problems remain polynomially solvable.
---
paper_title: A makespan study of the two-machine flowshop scheduling problem with a learning effect

paper_content:

Abstract This paper studies the problem of minimizing the makespan in a two-machine flowshop scheduling problem with learning considerations. Johnson’s rule might not provide the optimal solution for this problem. Thus, this paper not only develops several dominance relations and proposes a branch-and-bound algorithm based on them but also establishes two heuristic algorithms. Computational experiments show the accuracy of Johnson’s rule and both proposed heuristics, and a comparison of the results to the optimal solution obtained by a branch-and-bound technique is provided for small job sizes. In addition, the performances of the three heuristics, including Johnson’s rule, are also reported for large job sizes.
---
paper_title: Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs

paper_content:

Abstract We consider a single machine scheduling problem in which the machine experiences the effects of learning of fatigue as it continues to work and the jobs have due dates and are subject to penalties if they are not completed on time. Because of the effects of learning or fatigue, the performance rate of the machine varies over time. As a result, the processing time of a job depends on its work content as well as the total work content of the jobs completed prior to its loading. In this paper, we prove that even when the machine works at a variable rate, the pair-wise interchange of jobs minimizes the maximum tardiness and a simple modification to the well-known Moore-Hodgson's algorithm yields the minimum number of tardy jobs. Further, we formulate the problem of minimizing the total penalty for tardy jobs as a 0–1 knapsack problem with nested constraints, and solve it by using dynamic programming recursion as well as the maximum-weighted network path algorithm. Then we combine these two techniques and solve the 0–1 knapsack problem, by inducing a nested constraint structure and constructing a network with fewer nodes.
---
paper_title: Minimizing Flow Time on Parallel Identical Processors with Variable Unit Processing Time

paper_content:

We show that minimizing total flow time on parallel identical processors with nonincreasing unit processing time is achieved with shortest processing time SPT scheduling: Sequence the tasks in an order of nondecreasing lengths. Following this order and starting with the shortest task, process any task by the first processor that becomes available. If the unit processing time is allowed to be increasing, e.g., quadratically, the problem becomes NP-hard.
---
paper_title: Soft Due Window Assignment and Scheduling on Parallel Machines

paper_content:

We study problems of scheduling jobs on identical parallel machines, in which a due window has to be assigned to each job. If a job is completed within its due window, then it incurs no scheduling cost. Otherwise, it incurs earliness or tardiness cost. Two due window models are considered. In both models, the due window size is a decision variable common for all jobs. In the first model, called a constant due window, the due window starting time is a decision variable common for all jobs, and in the second, called a slack due window, the due window starting time is equal to the job processing time plus a decision variable common for all jobs. The objective is to find a job schedule as well as the size and location(s) of the due window(s) such that a weighted maximum or sum of costs associated with job earliness, job tardiness, and due window size is minimized. We establish the properties of optimal solutions of these minmax and minsum problems. For a constant due window model, we prove that the minmax problem with arbitrary weights and the minsum problem with equal weights are polynomially equivalent to the classical parallel machine scheduling problem to minimize the makespan. We further show that the problems for a constant due window model and slack due window model with the same objective function are reversible in the sense that their optimal solutions are mirror images of each other. These results imply O(n) and O(n log n) time algorithms for the considered problems when m=1.
---
paper_title: COMMON DUE-WINDOW SCHEDULING

paper_content:

In this paper, we solve common due-window scheduling problems within the just-in-time window concept, i.e., scheduling problems including both earliness and tardiness penalties. We assume that jobs share the same due window and incur no penalty as long as they are completed within the due window. We further assume that the earliness and tardiness penalty factors are constant and that the size of the window is a given parameter. ::: ::: ::: ::: For cases where the location of the due window is a decision variable, we provide a polynomial algorithm with complexity O(n * log (n)) to solve the problem. For cases where the location of the due window is a given parameter, we use dynamic programming with pseudopolynomial complexity to solve the problem.
---
paper_title: Common due window size and location determination in a single machine scheduling problem

paper_content:

We consider a single machine static and deterministic scheduling problem in which jobs have a common due window. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The objective is to find the optimal size and location of the window as well as an optimal sequence to minimise a cost function based on earliness, tardiness, window size, and window location. We propose an O(n log n) algorithm to solve the problem.
---
paper_title: Single processor scheduling problems with various models of a due window assignment

paper_content:

In the paper we investigate four single processor scheduling problems, which deal with the process of the negotiation between a producer and a customer about delivery time of final products. This process is modeled by a due window, which is a generalization of well known classical due date and describes a time interval, in which a job should be finished. Due window assignment is a new approach, which has been investigated in the scientific literature for a few years. In this paper we consider various models of due window assignment. To solve the formulated problems we have to find such a schedule of jobs and such an assignment of due windows to each job, which minimizes a given criterion dependent on the maximum or total earliness and tardiness of jobs and due window parameters. One of the main results is the mirror image of the solutions of the considered problems and other problems presented in the scientific literature. The wide survey of the literature is also given.
---

Title: Scheduling problems with a common due window assignment: A survey
Section 1: Introduction
Description 1: This section introduces the context and importance of the scheduling problems with a common due window assignment, elaborating on the practical applications and challenges faced in the manufacturing systems.

Section 2: Problem notation
Description 2: This section presents the problem notation used in the paper, defining key variables and parameters essential for understanding the scheduling problems discussed.

Section 3: Classical models with job-independent earliness/tardiness penalty functions
Description 3: This section analyzes the problems with common due window assignment and job-independent earliness/tardiness penalty functions, discussing various sum type criteria and min-max type criteria.

Section 4: Classical models with job-dependent earliness/tardiness penalty functions
Description 4: This section delves into more complex scheduling problems with job-dependent penalty functions, discussing various models and their computational complexities.

Section 5: Other models
Description 5: This section explores scheduling models with a common due window assignment extended to include additional complexities like changeable job processing times, deteriorating jobs, learning and aging effects, and maintenance activities.

Section 6: Discussion and recommendations
Description 6: This section discusses the current state of research, practical applications, and provides recommendations for future studies, emphasizing the need for real-life examples in certain models.

Section 7: Conclusion
Description 7: This section presents a summary of the state of the art in scheduling problems with a common due window assignment and earliness/tardiness penalty functions, along with observations on computational complexities and solution algorithms.