Scheduling jobs with different,job-dependent earliness and tardiness penalties using the SLK method

The single machine job scheduling problem, where due dates are assigned using the SLK due date determination method, is examined assuming different penalties for the early and tardy jobs. These penalties are assumed to be job-dependent, proportional to the processing times of jobs raised to an integer, non-negative power. The objective function is the total weighted lateness. Several cases are examined and four algorithms providing the optimal sequences for these cases are presented. Examples are given and conclusions are drawn.     

Scheduling jobs on a machine subject to stochastic breakdowns to minimize absolute early-tardy penalties

This article addresses the problem of scheduling n jobs with a common due date on a machine subject to stochastic breakdowns to minimize absolute early-tardy penalties.We investigate the problem under the conditions that the uptimes follow an exponential distribution,and the objective measure in detail is to minimize the expected sum of the absolute deviations of completion times from the common due date.We proceed to study in two versions (the downtime follows an exponential distribution or is a constant entailed for the repeat model job),one of which is the so-called preempt- resume version,the other of which is the preempt-repeat version.Three terms of work have been done.(i)Formulations and Preliminaries.A few of necessary definitions,relations and basic facts are established.In particular,the conclusion that the expectation of the absolute deviation of the completion time about a job with deterministic processing time t from a due date is a semi-V-shape function in t has been proved.(ii) Properties of Optimal Solutions.A few characteristics of optimal solutions are established.Most importantly,the conclusion that optimal solutions possess semi-V- shape property has been proved.(iii) Algorithm.Some computing problems on searching for optimal solutions are discussed.     

Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs

This paper studies the problem of simultaneous due-date determination and sequencing of a set of n jobs on a single machine where processing times are random variables and job earliness and tardiness costs are distinct. The objective is to determine the optimal sequence and the optimal due-dates which jointly minimize the expected total earliness and tardiness cost. We present an analytical approach to determine optimal due-dates, and propose two efficient heuristics of order O(n log n) to find candidates for the optimal sequence. It is demonstrated that variations in processing times increase cost and affect sequencing and due-date determination decisions. Our illustrative examples as well as computational results show that the proposed model produces optimal sequences and optimal due-dates that are significantly different from those provided by the classical deterministic single machine models. Furthermore, our computational experiments reveal that the proposed heuristics perform well in providing either optimal sequences or good candidates with low overcosts.     

Single machine scheduling to minimize weighted earliness subject to no tardy jobs

This paper considers the single machine scheduling problem where the objective is to minimize the total weighted earliness subject to no tardy jobs. Known results for a well researched single machine scheduling problem where the objective is to minimize the weighted completion time subject to no tardy jobs have been used in analyzing this problem. Several important results are proved and both exact and approximate methods are developed to solve this problem.     

Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties

We consider a single-machine scheduling problem with linear decreasing deterioration in which the due dates are determined by the equal slack (SLK) method. By the linear decreasing deterioration, we mean that the job’s processing time is a decreasing function of its starting time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function.     

Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs

Motivated by just-in-time manufacturing, we consider a single machine scheduling problem with dual criteria, i.e., the minimization of the total weighted earliness subject to minimum number of tardy jobs. We discuss several dominance properties of optimal solutions. We then develop a heuristic algorithm with time complexity O(n³) and a branch and bound algorithm to solve the problem. The computational experiments show that the heuristic algorithm is effective in terms of solution quality in many instances while the branch and bound algorithm is efficient for medium-size problems.     

Scheduling a single machine with multiple job processing ability to minimize makespan

This paper investigates a new problem, called single machine scheduling with multiple job processing ability, which is derived from the production of the continuous walking beaming reheating furnace in iron and steel industry. In this problem, there is no batch and the jobs enter and leave the machine one by one and continuously, which is different from general single machine batch scheduling problem where the jobs in a batch share the same start and departure time. Therefore, the start time and the departure time of a job depend on not only the job sequence but also the machine capacity. This problem is also different from the single semi-continuous batching machine scheduling recently studied in the literature, where the jobs are processed in batch mode and a new batch cannot be started for processing until the processing of the previous batch is completed though jobs in the same batch enter and leave the machine one by one. The objective of this problem is to minimize the makespan. We formulate this problem as a mixed integer linear programming model and propose a particle swarm optimization (PSO) algorithm for this problem. Computational results on randomly generated instances show that the proposed PSO algorithm is effective.     

Scheduling to minimize maximum earliness and number of tardy jobs where machine idle time is allowed

We address the bicriteria problem of minimizing the number of tardy jobs and maximum earliness on a single machine where machine idle time is allowed. We show that the problem of minimizing the number of tardy jobs while maximum earliness is kept at its minimum value of zero is polynomially solvable. We present polynomial time algorithms for the maximum earliness problem subject to no tardy jobs and the maximum earliness problem for a given set of tardy jobs. Finally, we discuss the use of the latter algorithm in generating all efficient schedules.     

Scheduling multiple orders per job in a single machine to minimize total completion time

This paper deals with a single-machine scheduling problem with multiple orders per job (MOJ) considerations. Both lot processing machines and item processing machines are also examined. There are two primary decisions that must be made in the proposed problem: (1) how to group the orders together, and (2) how to schedule the jobs once they are formed. In order to obtain the optimal solution to a scheduling problem, these two decisions should be made simultaneously. The performance measure is the total completion time of all orders. Two mixed binary integer programming models are developed to optimally solve this problem. Also, two efficient heuristics are proposed for solving large-sized problems. Computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics.     

Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan

This study addresses a single machine scheduling problem with periodic maintenance, where the machine is assumed to be stopped periodically for maintenance for a constant time w during the scheduling period. Meanwhile, the maintenance period [u, v] is assumed to have been previously arranged and the time w is assumed not to exceed the available maintenance period [u, v] (i.e. w ? v − u). The time u(v) is the earliest (latest) time at which the machine starts (stops) its maintenance. The objective is to minimize the makespan. Two mixed binary integer programming (BIP) models are provided for deriving the optimal solution. Additionally, an efficient heuristic is proposed for finding the near-optimal solution for large-sized problems. Finally, computational results are provided to demonstrate the efficiency of the models and the effectiveness of the heuristics. The mixed BIP model can optimally solve up to 100-job instances, while the average percentage error of the heuristic is below 1%.     

Scheduling about a common due date with kob-dependent asymmetric earliness and tardiness penalties

This paper is concerned with the problem of scheduling n jobs with a common due date on a single machine so as to minimize the total cost arising from earliness and tardiness. A general model is examined, in which earliness penalty and tardiness penalty are, respectively, arbitrary non-decreasing functions. Moreover, the model includes two important features that commonly appear in practical problems, namely, 1) earliness and tardiness are penalized with different weights which are job-dependent, and 2) the earliness (or tardiness) penalty consists of two parts, one is a variable cost dependent on the length of earliness (or tardiness), while the other is a fixed cost incurred when a job is early (or tardy). This model provides a general and flexible performance measure for earliness/tardiness scheduling, which has not been addressed before. We establish a number of results on the characterizations of optimal and sub-optimal solutions, and propose two algorithms based on these results. The first algorithm can find, under an agreeable weight condition, an optimum in time O(n² P_n), and the second algorithm can generate a sub-optimum in time O(nP_n), where P_n is the sum of the processing times. Further, we derive an upper bound on the relative error of the sub-optimal solution and show that, under certain conditions, the error tends to zero as n increases. Computational results are also reported to demonstrate the effectiveness of the algorithms proposed.     

Stochastic single machine scheduling subject to machines breakdowns with quadratic early-tardy penalties for the preemptive-repeat model

In this paper we research the problem in which the objective is to minimize the sum of squared deviations of job expected completion times from the due date, and the job processing times are stochastic. In the problem the machine is subject to stochastic breakdowns and all jobs are preempt-repeat. In order to show that the replacing ESSD by SSDE is reasonable, we discuss difference between ESSD function and SSDE function. We first give an express of the expected completion times for both cases without resampling and with resampling. Then we show that the optimal sequence of the problem V-shaped with respect to expected occupying time. A dynamic programming algorithm based on the V-shape property of the optimal sequence is suggested. The time complexity of the algorithm is pseudopolynomial.     

Single machine scheduling with family setups to minimize total earliness and tardiness

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize total earliness and tardiness when family setup times exist. The paper proposes optimal branch-and-bound algorithms for both the group technology assumption and if the group technology assumption is removed. A heuristic algorithm is proposed to solve larger problems with the group technology assumption removed. The proposed algorithms were empirically evaluated on problems of various sizes and parameters. The paper also explores how the choice of procedure affects total earliness and tardiness if an implementation of lean production methods has resulted in a reduction in setup times. An important finding of these empirical investigations is that scheduling jobs by removing the group technology assumption can significantly reduce total earliness and tardiness.     

Scheduling jobs with release times preemptively on a single machine to minimize the number of late jobs

We give a direct combinatorial O(n³logn) algorithm for minimizing the number of late jobs on a single machine when jobs have release times and preemptions are allowed. Our algorithm improves the earlier O(n⁵) and O(n⁴) dynamic programming algorithms for this problem.     

Scheduling problems with two competing agents to minimize minmax and minsum earliness measures

A relatively new class of scheduling problems consists of multiple agents who compete on the use of a common processor. We focus in this paper on a two-agent setting. Each of the agents has a set of jobs to be processed on the same processor, and each of the agents wants to minimize a measure which depends on the completion times of its own jobs. The goal is to schedule the jobs such that the combined schedule performs well with respect to the measures of both agents. We consider measures of minmax and minsum earliness. Specifically, we focus on minimizing maximum earliness cost or total (weighted) earliness cost of one agent, subject to an upper bound on the maximum earliness cost of the other agent. We introduce a polynomial-time solution for the minmax problem, and prove NP-hardness for the weighted minsum case. The unweighted minsum problem is shown to have a polynomial-time solution.     

Batch scheduling and common due-date assignment on a single machine

We consider the problem of scheduling n groups of jobs on a single machine where three types of decisions are combined: scheduling, batching and due-date assignment. Each group includes identical jobs and may be split into batches; jobs within each batch are processed jointly. A sequence independent machine set-up time is needed between each two consecutively scheduled batches of different groups. A due-date common to all jobs has to be assigned. A schedule specifies the size of each batch, i.e. the number of jobs it contains, and a processing order for the batches. The objective is to determine a value for the common due-date and a schedule so as to minimize the sum of the due date assignment penalty and the weighted number of tardy jobs. Several special cases of this problem are shown to be ordinary NP-hard. Some cases are solved in O(n log n) time. Two pseudopolynomial dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.     

Scheduling tasks on a flexible manufacturing machine to minimize tool change delays

This paper considers the problem of scheduling a given set of precedence constraint tasks on a flexible machine equipped with a tool magazine where each task requires exactly one of the tools during its execution. Changing from one tool to another requires a certain amount of time that depends on the pair of tools being exchanged. We present a new algorithmic approach for general task precedence relations when it is desired to sequence the tasks in such a way that the total time required for tool changes is minimized. The proposed algorithm is of polynomial time complexity in case of task precedences of limited width w, i.e. for precedence relations where each subset of independent tasks has not more than w elements. Since the task precedences width w could be arbitrary, we describe two heuristic algorithms and empirically evaluate their effectiveness in finding schedules with minimum total time required for tool changes.     

Scheduling uniform parallel machines subject to a secondary resource to minimize the number of tardy jobs

This research investigates the problem of scheduling jobs on a set of parallel machines where the speed of the machines depends on the allocation of a secondary resource. The secondary resource is fixed in quantity and is to be allocated to the machines at the start of the schedule. The scheduling objective is to minimize the number of tardy jobs. Two versions of the problem are analyzed. The first version assumes that the jobs are pre-assigned to the machines, while the second one takes into consideration the task of assigning jobs to the machines. The paper proposes an Integer Programming formulation to solve the first case and a set of heuristics for the second.     

Scheduling the maintenance on a single machine

This paper considers a single machine scheduling problem with preventive maintenance. In many cases, a machine must be maintained after it continuously works for a period of time. But most papers in the literature ignore non-availability of the machine. For this reason, this paper studies the problem of scheduling processing of jobs and maintenance of machine simultaneously. The objective is to minimise total completion time of jobs. The problem is proved to be NP-hard in the strong sense. Three heuristic algorithms and a branch and bound algorithm are proposed. Computational experiments are done to evaluate the effectiveness of the algorithms.     

Minimizing makespan on a single machine subject to random breakdowns

We investigate optimal sequencing policies for the expected makespan problem with an unreliable machine, where jobs have to be reprocessed in their entirety if preemptions occur because of breakdowns. We identify a class of uptime distributions under which LPT minimizes expected makespan.