Scheduling with inserted idle time: problem taxonomy and literature review
---
paper_title: A New Dominance Concept in Scheduling n Jobs on a Single Machine with Ready Times and Due Dates

paper_content:

Scheduling a set of jobs on a single machine is studied where each job has a specified ready time and due date (limit times). A dominance relationship is established within the set of possible sequences and results in an important restriction of the number of sequences to be considered in solving the feasibility problem. Establishing the dominance relationship leading to this restriction requires only the ordering of ready times and due dates and is thus independent of job processing times and of any change in limit times which does not affect the given order.
---
paper_title: A Forward-Backward Procedure for the Single Machine Problem to Minimize Maximum Lateness

paper_content:

Abstract This paper presents an optimal procedure for sequencing n jobs on one machine to minimize the maximum lateness when they may have different ready times, processing times, and due dates. This procedure is significantly more efficient for difficult problems than the McMahon/Florian algorithm which has achieved the best results in this area to date. The primary measures of computational efficiency for these procedures are the mean computer processing time and the percentage of problems solved optimally within a given time limit. An experiment that employs response surface methodology to locate problems within the region of highest difficulty shows the comparative efficiency of this procedure.
---
paper_title: Complexity of machine scheduling problems

paper_content:

We survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness we give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems. We finally discuss some questions that remain unanswered.
---
paper_title: The one-machine sequencing problem

paper_content:

Let M 1 and M 3 be non-bottleneck machines and M 2 a bottleneck machine processing only one job at a time. Suppose that n jobs have to be processed on M 1 , M 2 and M 1 (in that order) and job i has to spend a time a , on M 1 , d 1 on M 2 and q 1 on M 3 : we want to minimize the makespan. This problem is important since its resolution provides a bound on the makespan of complicated systems such as job shops. It is NP-hard in the strong sense. However, efficient branch and bound methods exist and we describe one of them. Our bound for the tree-search is very close to the bound used by Florian et al., but the principle of branching is quite different. At every node, we construct by an O( n log n ) algorithm a Schrage schedule; then we define a critical job c , a critical set J and consider two subsets of schedules; the schedules when c procedes every job of J and the schedules when c follows every job of J . We give the results of this method and prove that the difference between the optimum and the Schrage schedule is less than d 1 .
---
paper_title: On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness

paper_content:

An algorithm is developed for sequencing jobs on a single processor in order to minimize maximum lateness, subject to ready times and due dates. The method that we develop could be classified as branch-and-bound. However, it has the unusual feature that a complete solution is associated with each node of the enumeration tree.
---
paper_title: Algorithms for Solving Production-Scheduling Problems

paper_content:

Algorithms are developed for solving problems to minimize the length of production schedules. The algorithms generate anyone, or all, schedules of a particular subset of all possible schedules, called the active schedules. This subset contains, in turn, a subset of the optimal schedules. It is further shown that every optimal schedule is equivalent to an active optimal schedule. Computational experience with the algorithms shows that it is practical, in problems of small size, to generate the complete set of all active schedules and to pick the optimal schedules directly from this set and, when this is not practical, to random sample from the bet of all active schedules and, thus, to produce schedules that are optimal with a probability as close to unity as is desired. The basic algorithm can also generate the particular schedules produced by well-known machine loading rules.
---
paper_title: Tactically delayed versus non-delay scheduling: An experimental investigation☆

paper_content:

Abstract This paper compares tatically delayed scheduling to non-delay scheduling. While both of these types of schedules belong to the class of active schedules, tactically delayed schedules have the feature of introducing deliberate idle periods into the schedule. Non-delay schedules permit no such delays. To compare these scheduling methods, a number of sample single-machine problems are analyzed. For each problem, all possible non-delay and tactically delayed schedules are enumerated and the resulting tardiness of each schedule is recorded. Non-delay schedules are found to be considerably less numerous with lower total tardiness on average. Tactically delayed schedules appear to have better best case behavior than non-delay schedules. The results here allure further research into active scheduling methods.
---
paper_title: Sequencing with Earliness and Tardiness Penalties: A Review

paper_content:

We consider the problem of scheduling n jobs to minimize the total earliness and tardiness penalty. We review the literature on this topic, providing a framework to show how results have been generalized starting with a basic model that contains symmetric penalties, one machine and a common due date. To this base we add such features as parallel machines, complex penalty functions and distinct due dates. We also consolidate many of the existing results by proving general forms of two key properties of earliness/tardiness models.
---
paper_title: Cost-Based Scheduling of Workers and Equipment in a Fabrication and Assembly Shop

paper_content:

Many manufacturing firms that use Material Requirements Planning MRP cannot deliver products on schedule and within budget. Faced with bewildering bottlenecks, erratic process flows, and unrealistic due dates, they are unable to develop accurate schedules for their raw material acquisitions, workforce, and equipment. Their MRP plans must be translated into a workable schedule, one which determines when individual tasks will be performed by workers at work centers. There is a clear need for such an enhancement to MRP, a means to operate on detailed task data, yet capable of producing a schedule that directly relates to the MRP plan, the master production schedule, and the resource plan. We describe a method for determining feasible and cost-effective schedules for both labor and machines in a job shop. The method first sequences tasks at resources and then minimizes overall earliness and lateness cost by solving a series of maximum flow problems. By using the model as an enhancement to a company's MRP system, we simulated the cost effects of redeploying its workforce. Although the model was not used for real-time scheduling, it served a strategic role in workforce expansion and deployment decisions.
---
paper_title: Complexity of machine scheduling problems

paper_content:

We survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness we give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems. We finally discuss some questions that remain unanswered.
---
paper_title: Algorithms for a class of single-machine weighted tardiness and earliness problems

paper_content:

Abstract We address the problem of determining schedules for static, single-machine scheduling problems where the objective is to minimize the sum of weighted tardiness and weighted earliness. We develop optimal and heuristic procedures for the special case of weights that are proportional to the processing times of the respective jobs. The optimal procedure uses dominance properties to reduce the number of sequences that must be considered, and some of the heuristic use these properties as a basis for constructing good initial sequences. A pairwise interchange procedure is used to improve the heuristic solutions. An experimental study shows that the heuristic procedures perform very well.
---
paper_title: Minimizing mean tardiness and earliness in single‐machine scheduling problems with unequal due dates

paper_content:

We consider a single-machine scheduling problem with the objective of minimizing the mean (or equivalently, total) tardiness and earliness when due dates may differ among jobs. Some properties of the optimal solution are discussed, and these properties are used to develop both optimal and heuristic algorithms. Results of computational tests indicate that optimal solutions can be found for problems with up to 20 jobs, and that two of the heuristic procedures provide optimal or very near optimal solutions in many instances. © 1994 John Wiley & Sons, Inc.
---
paper_title: Single-machine scheduling with early and tardy completion costs

paper_content:

We address a single-machine scheduling problem in which penalties are assigned for early and tardy completion of jobs. These penalties are common in industrial settings where early job completion can cause the cash commitment to resources in a time frame earlier than needed, giving rise to early completion penalties. Tardiness penalties arise from a variety of sources, such as loss of customer goodwill, opportunity costs of lost sales, and direct cash penalties. Accounting for earliness cost makes the performance measure nonregular, and this nonregularity has apparently discouraged researchers from seeking solutions to this problem. We found that it is not much more difficult to design an enumerative search for this problem than it would be if the performance measure were regular. We present and demonstrate an efficient timetabling procedure which can be embedded in an enumerative algorithm allowing the search to be conducted over the domain of job permutations.© 1993 John Wiley & Sons, Inc.
---
paper_title: Minimizing Total Tardiness on One Machine is NP-Hard

paper_content:

The problem of minimizing the total tardiness for a set of independent jobs on one machine is considered. Lawler has given a pseudo-polynomial-time algorithm to solve this problem. In spite of extensive research efforts for more than a decade, the question of whether it can be solved in polynomial time or it is NP-hard in the ordinary sense remained open. In this paper the problem is shown to be NP-hard in the ordinary sense.
---
paper_title: Optimal timing schedules in earliness-tardiness single machine sequencing

paper_content:

The article deals with a single machine earliness-tardiness scheduling model where idle times are permitted in job processing. Based on a cluster concept we develop properties of the model that lead to a very fast algorithm to find an optimal timing schedule for a given sequence of jobs. The performance of this algorithm is tested on 480 randomly generated problems involving 100, 200, 400 and 500 jobs. It takes less than two seconds to solve a 500 job problem on a PC.
---
paper_title: THE SINGLE MACHINE EARLY / TARDY PROBLEM *

paper_content:

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs. Two dispatch priority rules are proposed and tested for this NP-complete problem. These were found to perform far better than known heuristics that ignored early costs. For situations where the potential cost savings are sufficiently high to justify more sophisticated techniques, we propose a variation of the Beam Search method developed by researchers in artificial intelligence. This variant, called Filtered Beam Search, is able to use priority functions to search a number of solution paths in parallel. A computational study showed that this search method was not only efficient but also consistent in providing near-optimal solutions with a relatively small search tree. The study also includes an investigation of the impacts of Beam Search parameters on three variations of Beam Search for this problem.
---
paper_title: A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems☆

paper_content:

Abstract We consider the dynamic single-machine scheduling problem where the objective is to minimize the sum of weighted earliness and weighted tardiness costs. A single pass heuristic, based on decision theory, is developed for constructing schedules. The heuristic permits schedules with idle time between jobs and behaves like a dispatching procedure. The performance of the new heuristic is examined using 116 published problems for which the optimum solution is known. Its performance is also investigated using 540 randomly generated problems covering a variety of conditions by comparing it to two well known dispatching procedures, adapted for dynamic early/tardy problems. The results indicate that the heuristic performs very well.
---
paper_title: One-processor scheduling with symmetric earliness and tardiness penalties

paper_content:

We consider one-processor scheduling problems having the following form: Tasks T1, T2,..., TN are given, with each Ti having a specified length li and a preferred starting time ai or, equivalently, a preferred completion time bi. The tasks are to be scheduled nonpreemptively i.e., a task cannot be split on a single processor to begin as close to their preferred starting times as possible. We examine two different cost measures for such schedules, the sum of the absolute discrepancies from the preferred starting times and the maximum such discrepancy. For the first of these, we show that the problem of finding minimum cost schedules is NP-complete; however, we give an efficient algorithm that finds minimum cost schedules whenever the tasks either all have the same length or are required to be executed in a given fixed sequence. For the second cost measure, we give an efficient algorithm that finds minimum cost schedules in general, with no constraints on the ordering or lengths of the tasks.
---
paper_title: Heuristic algorithms for solving earliness-tardiness scheduling problem with machine vacations

paper_content:

Abstract The earliness and tardiness (E/T) penalty problem in scheduling gained more importance in part due to its application in Just-In-Time (JIT) production system. Inorder to meet JIT production schedules preventive maintenance plan must be in place. During the maintenance periods machine is not available for processing. The time duration planned for preventive maintenance or meal breaks is called machine vacation. Incorporating E/T penalty and machine vacation a single machine scheduling model is developed. Heuristic methods for solving this problem and computational results are also presented.
---
paper_title: Preemptive scheduling of uniform machines subject to release dates

paper_content:

We shall be concerned with finding optimal preemptive schedules on parallel machines, subject to release dates for the jobs. Two polynomial-time algorithms are presented. The first algorithm minimizes maximum completion time on an arbitrary number of uniform machines. The second algorithm minimizes maximum lateness with respect to due dates for the jobs on an arbitrary number of identical machines or on two uniform machines. A third algorithm for minimizing maximum lateness on an arbitrary number of uniform machines is briefly discussed. NP-hardness is established for the problem of minimizing total weighted completion time on a single machine.
---
paper_title: Cost-Based Scheduling of Workers and Equipment in a Fabrication and Assembly Shop

paper_content:

Many manufacturing firms that use Material Requirements Planning MRP cannot deliver products on schedule and within budget. Faced with bewildering bottlenecks, erratic process flows, and unrealistic due dates, they are unable to develop accurate schedules for their raw material acquisitions, workforce, and equipment. Their MRP plans must be translated into a workable schedule, one which determines when individual tasks will be performed by workers at work centers. There is a clear need for such an enhancement to MRP, a means to operate on detailed task data, yet capable of producing a schedule that directly relates to the MRP plan, the master production schedule, and the resource plan. We describe a method for determining feasible and cost-effective schedules for both labor and machines in a job shop. The method first sequences tasks at resources and then minimizes overall earliness and lateness cost by solving a series of maximum flow problems. By using the model as an enhancement to a company's MRP system, we simulated the cost effects of redeploying its workforce. Although the model was not used for real-time scheduling, it served a strategic role in workforce expansion and deployment decisions.
---
paper_title: A New Dominance Concept in Scheduling n Jobs on a Single Machine with Ready Times and Due Dates

paper_content:

Scheduling a set of jobs on a single machine is studied where each job has a specified ready time and due date (limit times). A dominance relationship is established within the set of possible sequences and results in an important restriction of the number of sequences to be considered in solving the feasibility problem. Establishing the dominance relationship leading to this restriction requires only the ordering of ready times and due dates and is thus independent of job processing times and of any change in limit times which does not affect the given order.
---
paper_title: The one-machine sequencing problem

paper_content:

Let M 1 and M 3 be non-bottleneck machines and M 2 a bottleneck machine processing only one job at a time. Suppose that n jobs have to be processed on M 1 , M 2 and M 1 (in that order) and job i has to spend a time a , on M 1 , d 1 on M 2 and q 1 on M 3 : we want to minimize the makespan. This problem is important since its resolution provides a bound on the makespan of complicated systems such as job shops. It is NP-hard in the strong sense. However, efficient branch and bound methods exist and we describe one of them. Our bound for the tree-search is very close to the bound used by Florian et al., but the principle of branching is quite different. At every node, we construct by an O( n log n ) algorithm a Schrage schedule; then we define a critical job c , a critical set J and consider two subsets of schedules; the schedules when c procedes every job of J and the schedules when c follows every job of J . We give the results of this method and prove that the difference between the optimum and the Schrage schedule is less than d 1 .
---
paper_title: Algorithms for Solving Production-Scheduling Problems

paper_content:

Algorithms are developed for solving problems to minimize the length of production schedules. The algorithms generate anyone, or all, schedules of a particular subset of all possible schedules, called the active schedules. This subset contains, in turn, a subset of the optimal schedules. It is further shown that every optimal schedule is equivalent to an active optimal schedule. Computational experience with the algorithms shows that it is practical, in problems of small size, to generate the complete set of all active schedules and to pick the optimal schedules directly from this set and, when this is not practical, to random sample from the bet of all active schedules and, thus, to produce schedules that are optimal with a probability as close to unity as is desired. The basic algorithm can also generate the particular schedules produced by well-known machine loading rules.
---
paper_title: Scheduling of a single machine to minimize total weighted completion time subject to release dates

paper_content:

In this paper the n/1/rj ΣjwjCj problem under the assumptions of nonpreemptive sequencing and sequence independent processing times is investigated. After pointing out the fundamental properties, some dominance sufficient conditions among sequences are obtained and a branch and bound algorithm is proposed. Computational results are reported and discussed.
---
paper_title: Cost-Based Scheduling of Workers and Equipment in a Fabrication and Assembly Shop

paper_content:

Many manufacturing firms that use Material Requirements Planning MRP cannot deliver products on schedule and within budget. Faced with bewildering bottlenecks, erratic process flows, and unrealistic due dates, they are unable to develop accurate schedules for their raw material acquisitions, workforce, and equipment. Their MRP plans must be translated into a workable schedule, one which determines when individual tasks will be performed by workers at work centers. There is a clear need for such an enhancement to MRP, a means to operate on detailed task data, yet capable of producing a schedule that directly relates to the MRP plan, the master production schedule, and the resource plan. We describe a method for determining feasible and cost-effective schedules for both labor and machines in a job shop. The method first sequences tasks at resources and then minimizes overall earliness and lateness cost by solving a series of maximum flow problems. By using the model as an enhancement to a company's MRP system, we simulated the cost effects of redeploying its workforce. Although the model was not used for real-time scheduling, it served a strategic role in workforce expansion and deployment decisions.
---
paper_title: Algorithms for a class of single-machine weighted tardiness and earliness problems

paper_content:

Abstract We address the problem of determining schedules for static, single-machine scheduling problems where the objective is to minimize the sum of weighted tardiness and weighted earliness. We develop optimal and heuristic procedures for the special case of weights that are proportional to the processing times of the respective jobs. The optimal procedure uses dominance properties to reduce the number of sequences that must be considered, and some of the heuristic use these properties as a basis for constructing good initial sequences. A pairwise interchange procedure is used to improve the heuristic solutions. An experimental study shows that the heuristic procedures perform very well.
---
paper_title: Single-machine scheduling with early and tardy completion costs

paper_content:

We address a single-machine scheduling problem in which penalties are assigned for early and tardy completion of jobs. These penalties are common in industrial settings where early job completion can cause the cash commitment to resources in a time frame earlier than needed, giving rise to early completion penalties. Tardiness penalties arise from a variety of sources, such as loss of customer goodwill, opportunity costs of lost sales, and direct cash penalties. Accounting for earliness cost makes the performance measure nonregular, and this nonregularity has apparently discouraged researchers from seeking solutions to this problem. We found that it is not much more difficult to design an enumerative search for this problem than it would be if the performance measure were regular. We present and demonstrate an efficient timetabling procedure which can be embedded in an enumerative algorithm allowing the search to be conducted over the domain of job permutations.© 1993 John Wiley & Sons, Inc.
---
paper_title: Minimizing Total Tardiness on One Machine is NP-Hard

paper_content:

The problem of minimizing the total tardiness for a set of independent jobs on one machine is considered. Lawler has given a pseudo-polynomial-time algorithm to solve this problem. In spite of extensive research efforts for more than a decade, the question of whether it can be solved in polynomial time or it is NP-hard in the ordinary sense remained open. In this paper the problem is shown to be NP-hard in the ordinary sense.
---
paper_title: Optimal timing schedules in earliness-tardiness single machine sequencing

paper_content:

The article deals with a single machine earliness-tardiness scheduling model where idle times are permitted in job processing. Based on a cluster concept we develop properties of the model that lead to a very fast algorithm to find an optimal timing schedule for a given sequence of jobs. The performance of this algorithm is tested on 480 randomly generated problems involving 100, 200, 400 and 500 jobs. It takes less than two seconds to solve a 500 job problem on a PC.
---
paper_title: A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems☆

paper_content:

Abstract We consider the dynamic single-machine scheduling problem where the objective is to minimize the sum of weighted earliness and weighted tardiness costs. A single pass heuristic, based on decision theory, is developed for constructing schedules. The heuristic permits schedules with idle time between jobs and behaves like a dispatching procedure. The performance of the new heuristic is examined using 116 published problems for which the optimum solution is known. Its performance is also investigated using 540 randomly generated problems covering a variety of conditions by comparing it to two well known dispatching procedures, adapted for dynamic early/tardy problems. The results indicate that the heuristic performs very well.
---
paper_title: Scheduling of a single machine to minimize total weighted completion time subject to release dates

paper_content:

In this paper the n/1/rj ΣjwjCj problem under the assumptions of nonpreemptive sequencing and sequence independent processing times is investigated. After pointing out the fundamental properties, some dominance sufficient conditions among sequences are obtained and a branch and bound algorithm is proposed. Computational results are reported and discussed.
---
paper_title: Scheduling with neural networks: the case of the Hubble Space Telescope

paper_content:

Abstract Creating an optimum long-term schedule for the Hubble Space Telescope is difficult by almost any standard due to the large number of activities, many relative and absolute time constraints, prevailing uncertainties and an unusually wide range of timescales. This problem has motivated research in neural networks for scheduling. The novel concept of continuous suitaility functions defined over a continuous time domain has been developed to represent soft temporal relationships between activities. All constraints and preferences are automatically translated into the weights of an appropriately designed artificial neural network. The constraints are subject to propagation and consistency enhancement in order to increase the number of explicitly represented constraints. Equipped with a novel stochastic neuron update rule, the resulting GDS-network effectively implements a Las Vegas-type algorithm to generate good schedules with an unparalleled efficiency. When provided with feedback from execution the network allows dynamic schedule revision and repair.
---
paper_title: A decision theory based scheduling procedure for single-machine weighted earliness and tardiness problems☆

paper_content:

Abstract We consider the dynamic single-machine scheduling problem where the objective is to minimize the sum of weighted earliness and weighted tardiness costs. A single pass heuristic, based on decision theory, is developed for constructing schedules. The heuristic permits schedules with idle time between jobs and behaves like a dispatching procedure. The performance of the new heuristic is examined using 116 published problems for which the optimum solution is known. Its performance is also investigated using 540 randomly generated problems covering a variety of conditions by comparing it to two well known dispatching procedures, adapted for dynamic early/tardy problems. The results indicate that the heuristic performs very well.
---

Title: Scheduling with Inserted Idle Time: Problem Taxonomy and Literature Review
Section 1: INTRODUCTION
Description 1: Write the introduction and scope of inserted idle time (IIT) scheduling and its importance in production scheduling.

Section 2: THE LITERATURE OF IIT SCHEDULING
Description 2: Review the literature focusing on IIT scheduling and categorize it based on problem characteristics such as regular and nonregular performance measures.

Section 3: A TAXONOMY FOR IIT SCHEDULING PROBLEMS
Description 3: Present a taxonomy for classifying IIT scheduling problems based on various situational parameters and problem structures.

Section 4: Research Opportunities
Description 4: Discuss further research areas and opportunities in IIT scheduling, focusing on algorithm development, timetabling integration, and heuristic methods.

Section 5: Summary
Description 5: Summarize the key findings, the importance of IIT schedules, and potential areas for further research in the field.