Single machine due-window assignment scheduling with resource-dependent processing times to minimise total resource consumption cost

This paper considers a single-machine scheduling problem involving convex resource-dependent processing times and due-window assignment simultaneously. The goal is to minimise the total resource consumption cost under the constraint that the schedule cost involving earliness, tardiness, window location, window size and makespan does not exceed a given limit for two popular due window assignment methods: the common flow allowance (slack) due window assignment method (referred to SLKW) and the common due window assignment method (referred to CONW). We show that the problem can be solved in polynomial time. Some extensions of the problem are also given.     

Due date assignment in single machine with stochastic processing times

This paper considers two different due date assignment and sequencing problems in single machine where the processing times of jobs are random variables. The first problem is to minimise the maximum due date so that all jobs are stochastically on time. It is shown that sequencing the jobs in decreasing service level (DSL) order optimally solves the problem. The results are then extended for two special cases of flow shop problem. The other problem is to minimise a total cost function which is a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. The assignment of a common due date and distinct due dates are investigated for this problem. It is shown that the optimal sequence for the case of common due date is V-shaped.     

Single-machine common/slack due window assignment problems with linear decreasing processing times

This paper studies linear non-increasing processing times and the common/slack due window assignment problems on a single machine, where the actual processing time of a job is a linear non-increasing function of its starting time. The aim is to minimize the sum of the earliness cost, tardiness cost, due window location and due window size. Some optimality results are discussed for the common/slack due window assignment problems and two O(n log n) time algorithms are presented to solve the two problems. Finally, two examples are provided to illustrate the correctness of the corresponding algorithms.     

Due-date assignment scheduling involving job-dependent learning effects and convex resource allocation

ABSTRACT

This article addresses single machine resource allocation scheduling problems with learning effects, where learning effects mean job-dependent position-based learning effects. For the common due-date assignment (CON) and slack due-date assignment (SLK) methods, a bi-cost analysis of the scheduling cost and the total weighted resource consumption cost is provided. The objective is to determine the optimal job sequence and the resource allocation simultaneously, such that the scheduling cost (the total weighted resource consumption cost) is minimized subject to the total weighted resource consumption cost (the scheduling cost) being limited. Solution procedures are provided for the problems under consideration.     

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.     

Solution algorithms for the number of tardy jobs minimisation scheduling with a time-dependent learning effect

This paper deals with a single-machine scheduling problem with a time-dependent learning effect. The goal is to determine the job sequence that minimise the number of tardy jobs. Two dominance properties, two heuristic algorithms and a lower bound to speed up the search process of the branch-and-bound algorithm are proposed. Computational experiments show that the branch-and-bound algorithm can solve instances up to 18 jobs in a reasonable amount of time, and the proposed heuristic algorithm MFLA performs effectively and efficiently     

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.     

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.     

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.     

Proportionate flowshop scheduling with position-dependent weights

ABSTRACT

This article addresses proportionate flowshop scheduling problems with position-dependent weights wherein the weight is not related to the job but to the position in which the job is scheduled. Common and slack due date assignment models are discussed under a due date assignment framework. The goal is to determine a feasible schedule for all jobs and due dates of all jobs to minimize a total cost function wherein the objective function is of the minsum type. Optimal properties for the problems are proposed, based on which polynomial time algorithms are provided to solve these two problems optimally.