On Optimal Common Due-Date Determination

Given a set of n independent jobs to be processed on a singlemachine, the problem is to determine the optimal constant flowallowance for the CON due-date assignment method and the optimaljob sequence to minimize an average missed due-date cost. Alinear programming formulation of the problem is proposed andthe optimal due-date is obtained by solving the LP dual problem.It is shown that the optimal job sequence can be determinedanalytically only under a special circumstance. Finally, a numericalexample is given to demonstrate how the results can be appliedto find the optimal solutions.     

Setting Job-Shop Due-Dates with Service-Level Constraints

The job-shop due-date assignment problem arises when a manager needs to ‘promise’ a delivery date to a customer. Previous methods yield due-dates which are either optimistic (unlikely to be achieved) or conservative (the promise will be met, but too easily, because the date given was very pessimistic). This paper investigates the due-date assignment problem with a customer ‘service-level’ constraint, the percentage of time that promised delivery dates are honoured. We formulate a rule to attain this service level, yet maintain as short a due-date lead time as possible. Unlike previous attempts, this due-date rule considers not only the job content and instantaneous shop congestion information, but also implicitly incorporates information on how the jobs will be scheduled (or ‘loaded’) once they are in the shop. We simulate a single-machine shop for various measures of performance under several dispatching priorities, comparing our due-date rule with one reported to yield satisfactory performance. Our rule meets all requirements and is found to be superior for most measures of performance.     

Single-machine scheduling to minimize earliness and number of tardy jobs

This paper considers the problem of assigning a common due-date to a set of simultaneously available jobs and sequencing them on a single machine. The objective is to determine the optimal combination of the common due-date and job sequence that minimizes a cost function based on the assigned due-date, job earliness values, and number of tardy jobs. It is shown that the optimal due-date coincides with one of the job completion times. Conditions are derived to determine the optimal number of nontardy jobs. It is also shown that the optimal job sequence is one in which the nontardy jobs are arranged in nonincreasing order of processing times. An efficient algorithm of O(n logn) time complexity to find the optimal solution is presented and an illustrative example is provided. Finally, several extensions of the model are discussed.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG0036424. The authors are thankful to two anonymous referees for their constructive comments.     

Minmax scheduling problems with common flow-allowance

In due-date assignment problems with a common flow-allowance, the due-date of a given job is defined as the sum of its processing time and a job-independent constant. We study flow-allowance on a single machine, with an objective function of a minmax type. The total cost of a given job consists of its earliness/tardiness and its flow-allowance cost components. Thus, we seek the job schedule and flow-allowance value that minimize the largest cost among all the jobs. Three extensions are considered: the case of general position-dependent processing times, the model containing an explicit cost for the due-dates, and the setting of due-windows. Properties of optimal schedules are fully analysed in all cases, and all the problems are shown to have polynomial time solutions.     

A generalized activity network model

In recent years activity networks for projects with both random and deterministic alternative outcomes in key nodes have been considered. The developed control algorithm chooses an optimal outcome direction at every deterministic alternative node which is reached in the course of the project's realization. At each routine decision-making node, the algorithm singles out all the subnetworks (the so-called joint variants) which correspond to all possible outcomes from that node. Decision-making results in determining the optimal joint variant and following the optimal direction up to the next decision-making node. However, such models cover a limited class of alternative networks, namely, only fully-divisible networks which can be subdivided into nonintersecting fragments. In this paper, a more generalized activity network is considered. The model can be applied to a broader spectrum of R&D projects and can be used for all types of alternative networks, for example, for non-divisible networks comprising nodes with simultaneously ‘must follow’, random ‘exclusive OR’ and deterministic ‘exclusive or’ emitters. The branching activities of the third type refer to decision-making outcomes; choosing the optimal outcome is the sole prerogative of the project's management. Such a model is a more universal activity network; we will call it GAAN—Generalized Alternative Activity Network. The problem is to determine the joint variant optimizing the mean value of the objective function subject to restricted mean values of several other criteria. We will prove that such a problem is a NP-complete one. Thus, in general, the exact solution of the problem may be obtained only by looking through all the joint variants on the basis of their proper enumeration. To enumerate the joint variants we will use the lexicographical method in combination with some techniques of discrete optimization. A numerical example will be presented. Various application areas are considered.     

A Heuristic for Common Due-date Assignment and Job Scheduling on Parallel Machines

In this paper we consider the problem of scheduling a set of simultaneously available jobs on several parallel and identical machines. The problem is to find the optimal due-date, assuming this to be the same for all jobs. We also seek to sequence the jobs such that some are early and some are late so as to minimize a penalty function. For the single-machine problem, we present a simple proof of the well-known optimality result that the optimal due-date coincides with one of the job completion times. We show that the optimal job sequence for the single-machine problem can be easily determined. We prove that the same optimal due-date result can be generalized to the parallel-machine problem. However, determination of the optimal job sequence for such a problem is much more complex, and we present a simple heuristic to find an approximate solution. On the basis of a limited experiment, we observe that the heuristic is very effective in obtaining near-optimal solutions.     

A production planning model for an unreliable production facility: Case of finite horizon and single demand

We study a two-level inventory system that is subject to failures and repairs. The objective is to minimize the expected total cost so as to determine the production plan for a single quantity demand. The expected total cost consists of the inventory carrying costs for finished and unfinished items, the backlog cost for not meeting the demand due-date, and the planning costs associated with the ordering schedule of unfinished items. The production plan consists of the optimal number of lot sizes, the optimal size for each lot, the optimal ordering schedule for unfinished items, and the optimal due-date to be assigned to the demand. To gain insight, we solve special cases and use their results to device an efficient solution approach for the main model. The models are solved to optimality and the solution is either obtained in closed form or through very efficient algorithms.     

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.     

A due-date assignment problem with learning effect and deteriorating jobs

In this paper we consider a single-machine scheduling problem with the effects of learning and deterioration. In this model, job processing times are defined by functions of their starting times and positions in the sequence. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of earliness, tardiness and due-date. We show that the problem remains polynomially solvable under the proposed model.     

Optimal Assignment of Total-work-content Due-dates and Sequencing in a Single-machine Shop

This paper considers the problem of optimal assignment of total-work-content due-dates to n jobs and of sequencing them on a single machine to minimize an objective function depending on the assigned due-date multiple value and maximum tardiness penalty. It is shown that both the earliest due-date and shortest processing time orders yield an optimal sequence. A simple analytical solution method is presented to find the optimal due-dates. After the theoretical treatment an illustrative example is presented for discussion.     

Minimizing total completion time and total deviation of job completion times from a restrictive due-date

We study a single-machine scheduling problem with the objective of minimizing a linear combination of total job completion times and total deviation of job completion times from a common due-date. The due-date is assumed to be restrictive, i.e., it may be sufficiently small to have an impact on the optimal sequence. When more weight is allocated to total job completion times, the problem is shown to have a polynomial time solution. When more weight is allocated to total completion time deviations from the due-date, the problem is NP-hard in the ordinary sense. For the latter case, we introduce an efficient dynamic programming algorithm, which is shown numerically to perform well in all our tests.     

Due-date assignment and parallel-machine scheduling with deteriorating jobs

In this paper we study the problem of scheduling n deteriorating jobs on m identical parallel machines. Each job's processing time is a nondecreasing function of its start time. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of the due-date, earliness and tardiness penalties. We show that this problem is NP-hard, and we present a heuristic algorithm to find near-optimal solutions for the problem. When the due-date penalty is 0, we present a polynomial time algorithm to solve it.     

Minmax earliness–tardiness costs with unit processing time jobs

The problem addressed in this paper is defined by M parallel identical machines, N jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.     

Fairness versus efficiency in charging for the use of common facilities

The problem of efficiency vs fairness is considered in relation to the splitting of costs for shared facilities between users. This is considered as a result of a problem of sharing the cost of the provision of central computing facilities between different faculties in a large university, but the basic problem is widespread. A linear programming model is considered in order to minimise cost. The dual of this model is shown to correspond to an efficient allocation of costs. An alternative optimal dual solution is shown to give a ‘fair’ solution according to criteria resulting from cooperative game theory.     

The multiple-job repair kit problem

The repair kit problem is that of finding the optimal set of parts in the kit of a repairman. An important aspect of this problem, in many real-life situations, is that several job-sites are visited before a kit is restocked. In this paper, we present two heuristics for solving the multiple-job repair kit problem. Both heuristics can be used to determine a solution under the service-objective (minimal holding cost for a required job-fill rate) as well as the cost-objective (minimal expected total cost, including a penalty cost for each ‘broken’ job). They generate a series of kits ‘from empty to complete’ by adding one part at a time, and then select the kit with the smallest (approximate) total cost. The ‘Job Heuristic (JH)’ adds parts based on the ratio of holding cost to increase in job-fill rate, whereas the ‘Part Heuristic (PH)’ focuses on the ratio of holding cost to increase in the part-fill rate. Since part-fill rates are much easier to calculate, the PH is easier to apply. In fact, we show how it can be applied in a spreadsheet software package. The JH, however, is more exact. Indeed, it determines the optimal solution for all the examples (for which we are able to determine the optimal solution by complete search) considered in our numerical experiments. The PH also performs well. It generally has a cost error of less than 2% and determines the optimal solution in most cases, even if part failures are highly dependent. Based on these results, we recommend the use of the PH in practice.     

Scheduling under a common due-data on parallel unrelated machines

Due-data determination problems have gained significant attention in recent years due to the industrial focus in the just-in-time philosophy. In this paper the problem of scheduling a set of independent jobs on parallel unrelated processors under a common due-date is examined. The common due-date is a decision variable. The objective is to allocate and sequence the jobs on the machines and to determine the optimal due-data, so that the total cost be minimised. This cost is composed of the due-date assignment, the total earliness and the total tardiness cost. As the problem is NP-hard, a polynomial time heuristic procedure, which provides efficient solutions, is developed. The procedure is illustrated by means of an example and is tested via two small size experiments.     

Improving delivery reliability by a new due-date setting rule

We study the dynamic due-date setting problem where the objective is to improve delivery performance. Since the problem is NP-hard, we propose a simple, new, general, heuristic due-date setting procedure called the SL rule. For the classical M/M/1 queuing model, we analytically determine the optimum parameter for the proposed rule to achieve best due-date performance. We then show that the optimized SL rule outperforms the work-content-based TWK rule in terms of fraction tardy, mean tardiness, and mean earliness. Additional numerical and simulation analysis for a range of conditions, covering different shop workload levels and priority regimes, confirms that the proposed rule produces best due-date performance, compared to the work-content-based rule, under most of the conditions studied.     

Single Machine Scheduling with Flow Allowances

In this paper, a set of jobs is scheduled using the SLK due-date determination method, according to which all the jobs are given the same flow allowance. The single machine case is considered. The objective function is a cost function including three components, namely flow allowance and weighted earliness and tardiness. An analytical solution is given and an algorithm, which provides optimal solutions, is presented. Finally, the parallel machines case is discussed.     

Due-date assignment and single machine scheduling with deteriorating jobs

We study a scheduling problem with deteriorating jobs, that is, jobs whose processing times are an increasing function of their start times. We consider the case of a single machine and linear job-independent deterioration. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of due-date, earliness and tardiness penalties. We give an O(n log n) time algorithm to solve this problem.     

The directed polymer in a random environment

A continuous space/time approximation of the well known ‘directed polymer’ problem is considered. Connection between the ‘Helmholtz Free Energy’ and the ‘Two Walker problem’ is shown. Rigorous proof of the superdiffusive mean squared displacement exponent of 4/3 is given when there is one space dimension and one time dimension. Asymptotically diffusive behaviour of c(k)tis shown when there are one ‘time’ and two ‘space’ dimensions. For higher dimensions, the behaviour is diffusive and the mean squared displacement is asymptotically t d. These results hold for all temperature, because the phase transition in the discrete model is no longer present in the continuous model; the renormalization procedure has set the transition temperature to k _crit =0The joint distribution is also shown to be asymptotically sub-Gaussian for all dimensions and all temperatures (in the sense that the p ^thmoments as a function of pincrease more slowly than the moments of a Gaussian distribution). The ‘Helmholtz Free Energy’ is also calculated for this model and the quenched and annealed free energies are shown to be identical for all temperature