A note on single machine scheduling and due date assignment with general position-dependent processing times

This note considers single machine scheduling and due date assignment in which a job’s processing time depends on its position in a sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and the total earliness of the scheduled jobs. We analyse these problems with three different due date assignment methods. We provide a generic polynomial-time dynamic programming algorithm to solve the problems.     

No-wait two-machine permutation flow shop scheduling problem with learning effect,common due date and controllable job processing times

We consider a two-machine no-wait permutation flow shop common due date assignment scheduling problem where the processing time of a job is given as a function of its position in the sequence and its amount of resource allocated to this job. The common due date (CON) assignment method means that all the jobs are given a common due date. We need to make a decision on the common due date, resource allocation and the sequence of jobs to minimise total earliness, tardiness, common due date cost and total resource cost. We show that the problem remains polynomially solvable under the proposed model.     

Algorithms for the joint multitasking scheduling and common due date assignment problem

In this paper, we investigate a joint multitasking scheduling and common due date assignment problem on a single machine, for which examples can be found in product delivery process in logistics. Multitasking allows the machine to perform multiple tasks. The multitasking phenomenon has been observed in various practical domains, including manufacturing and administration. In multitasking settings, each waiting job interrupts a currently in-processing job, causing an interruption time and a switching time. In common due date assignment problems, the objective is to determine the optimal value of this due date with the purpose of minimising a total penalty function, which is associated with service quality. For the problem with general interruption functions, analytical properties are obtained to reduce the search space of the optimal solutions. For the cases with linear interruption functions, we develop a polynomial-time algorithm. Numerical experiments have been conducted to validate the efficiency of our proposed algorithm. Computational results also demonstrate an interesting phenomenon that in some cases, the optimal solutions under multitasking are superior to the counterparts without multitasking. Besides, we also devise a mixed integer programme for the cases with linear interruption function.     

Single-machine scheduling and common due date assignment with potential machine disruption

This paper studies a single-machine due date assignment and scheduling problem in a disruptive environment, where a machine disruption may occur at a particular time that will last for a period of time with a certain probability, and the job due dates are determined by the decision-maker using the popular common due date assignment method. The goal is to determine jointly the optimal job sequence and the common due date so as to minimise the expected value of an integrated cost function that includes the earliness, tardiness and due date assignment costs. We analyse the computational complexity status of various cases of the problem, and develop pseudo-polynomial-time solution algorithms, randomised adaptive search algorithms, and fully polynomial-time approximation schemes for them, if viable. Finally, we conduct extensive numerical testing to assess the performance of the proposed algorithms.     

Approximation algorithms for common due date assignment and job scheduling on parallel machines

We consider the problem of assigning a common due date to a set of jobs and scheduling the jobs on a set of parallel machines so that the weighted sum of the due date, total earliness, and total tardiness is minimized. A heuristic is developed to solve this problem, and an absolute performance ratio is provided for this heuristic. Another heuristic with a better worst-case performance bound is presented for the case with a zero earliness penalty. A fully polynomial approximation scheme is also developed.     

Error bound for common due date assignment and job scheduling on parallel machines

We consider a heuristic which has been applied to assign a common due date to a set of n jobs and schedule them on a set of m parallel and identical machines so that the weighted sum of the due date, earliness and tardiness is approximately minimized. We alter the heuristic slightly and show that the revised version is asymptotically optimal as n→∞.     

A double-layered optimisation approach for the integrated due date assignment and scheduling problem

As the market competition becomes fiercer, contemporary make-to-order firms are confronted with both due date quotation and production scheduling problems at the same time. On the one hand, in order to attract customers, the firm needs to quote a short lead time; on the other hand, once a due date has been promised, the firm must spare no effort to deliver the goods no later than this date. If due date assignment and shop scheduling are processed separately by two systems, the overall performance is unlikely to be satisfactory because the two tasks are actually interrelated (e.g. a tighter due date setting will increase the chances of tardiness despite its appeal for the incoming customer). Therefore, we consider the problem by integrating due date assignment and shop scheduling into one optimisation model. A double-layered heuristic optimisation algorithm is presented for solving this problem. In the upper-layer genetic algorithm which performs coarse-granularity optimisation, Bayesian networks are used to learn the distribution of optimal due date values. As the second-layer algorithm, a parameter perturbation method is applied for a finer-granularity neighbourhood search. Computational experiments prove the efficacy and efficiency of the proposed algorithm.     

Parallel machine scheduling about an unrestricted due date and additional resource constraints

This research considers the problem of schedulingjobs on parallel machines with an unrestricted due date and additional resources. The objective is to minimize the total absolute deviation of job completion times about the common due date. This problem is motivated by restrictions that occur in the handling and processing of jobs in certain phases of semiconductor manufacturing and other production systems. It is shown that the problem is polynomial when there exists one single type of additional resource and the resource requirements per job are zero or one.     

One-machine, N-product-type, continuous-time scheduling with a common due date: a polynomially solvable case

The paper analyzes a manufacturing system made up of one-machine which produces TV-product-types with controllable production rates in response to product demands. The demands are characterized by different amounts of each product-type to be produced and a common due date. The objective is to minimize inventory and backlog costs which are incurred when meeting the due date results in inventory surpluses and shortages. With the aid of the maximum principle, the continuous-time scheduling problem is studied as an optimal control model and is reduced to a combinatorial one, polynomially solvable when the costs are either “agreeable” or when the number of the non-agreeable costs is limited.     

Effect of granularity of resource availability on the accuracy of due date assignment

In a make-to-order environment, order due dates can be assigned by consecutively estimating for each task on the order the time that the required resource will be available to perform the task. This paper examines the nature of the trade-off between the granularity of representation of resource availability, the resulting accuracy of due dates, and the computational time required to compute a due date. Granularity is defined as the size of the intervals of time (time buckets) over which available capacity is computed in a discrete-time representation of resource availability. The literature does not provide guidance on setting this important parameter, and typically it is arbitrarily set to one day or one week. Results compiled from extensive computations show consistent patterns of behaviour across all six combinations of values of experimental parameters for order size variability and system utilization. The resulting behaviour is classified into seven regions and analysed. Interestingly, results indicate that as granularity decreases the accuracy increases only up to a point, and the accuracy for very small granularities actually can be much worse than the accuracy of moderate granularities. From the results it can be concluded that when granularity is set to an appropriate value, resource availability will be estimated with relatively high accuracy and relatively low computational time, which are important performance characteristics for an order promising application.     

Heuristic methods for the single machine scheduling problem with different ready times and a common due date

The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance is investigated. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs.     

Real time selection of scheduling rules and knowledge extraction via dynamically controlled data mining

A new scheduling system for selecting dispatching rules in real time is developed by combining the techniques of simulation, data mining, and statistical process control charts. The proposed scheduling system extracts knowledge from data coming from the manufacturing environment by constructing a decision tree, and selects a dispatching rule from the tree for each scheduling period. In addition, the system utilises the process control charts to monitor the performance of the decision tree and dynamically updates this decision tree whenever the manufacturing conditions change. This gives the proposed system the ability to adapt itself to changes in the manufacturing environment and improve the quality of its decisions. We implement the proposed system on a job shop problem, with the objective of minimising average tardiness, to evaluate its performance. Simulation results indicate that the performance of the proposed system is considerably better than other simulation-based single-pass and multi-pass scheduling algorithms available in the literature. We also illustrate knowledge extraction by presenting a sample decision tree from our experiments.     

Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect

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

Single CNC machine scheduling with controllable processing times and multiple due dates

In this study, we solve the single CNC machine scheduling problem with controllable processing times. Our objective is to maximize the total profit that is composed of the revenue generated by the set of scheduled jobs minus the sum of total weighted earliness and weighted tardiness, tooling and machining costs. Customers offer multiple due dates to the manufacturer, each coming with a distinct price for the order that is decreasing as the date gets later, and the manufacturer has the flexibility to accept or reject the orders. We propose a number of ranking rules and scheduling algorithms that we employ in a four-stage heuristic algorithm that determines the processing times for each job and a final schedule for the accepted jobs simultaneously, to maximize the overall profit.     

The burn-in test scheduling problem with batch dependent processing time and sequence dependent setup time

The burn-in test scheduling problem (BTSP) is a variation of the complex batch processing machine scheduling problem, which is also a generalisation of the liquid crystal injection scheduling problem with incompatible product families and classical identical parallel machine problem. In the case we investigated on the BTSP, the jobs are clustered by their product families. The product families can be clustered by different product groups. In the same product group, jobs with different product families can be processed as a batch. The batch processing time is dependent on the longest processing time of those jobs in that batch. Setup times between two consecutive batches of different product groups on the same batch machine are sequentially dependent. In addition, the unequal ready times are considered in the BTSP which involves the decisions of batch formation and batch scheduling in order to minimise the total machine workload without violating due dates and the limited machine capacity restrictions. Since the BTSP involves constraints on unequal ready time, batch dependent processing time, and sequence dependent setup times, it is more difficult to solve than the classical parallel batch processing machine scheduling problem with compatible product families or incompatible product families. These restrictions mean that the existing methods cannot be applied into real-world factories directly. Consequently, this paper proposes a mixed integer programming model to solve the BTSP exactly. In addition, two efficient solution procedures which solve the BTSP are also presented.     

Minimising earliness and tardiness penalties in single machine scheduling against common due date using imperialist competitive algorithm

In this paper a novel evolutionary-based approach is utilised for efficiently solving the NP-hard problem of scheduling numerous common-due-date jobs on a single machine. Minimising the sum of earliness and tardiness penalties for all jobs is considered as the target function. The performance of the proposed approach is examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs where the numerical results indicate that it can produce ‘better’ solutions in less computational time when compared to benchmark results and the methods available in the literature, namely genetic algorithm (GA), Tabu search (TS) and differential evolution (DE).