Due-window assignment and scheduling with general position-dependent processing times involving a deteriorating and compressible maintenance activity

In this paper, we consider common due-window assignment and scheduling problems with general position-dependent processing times involving deteriorating and compressible maintenance activity on a single machine. Two models associated with maintenance activity are examined in this article, in which the maintenance length is assumed to be either time-dependent and compressible or position-dependent and compressible. The objective is to find jointly the location and size of due-window, position of maintenance as well as resource amount allocated to it, and job sequence to minimise a total cost function based on earliness, tardiness, window location, window size and resource cost. We show that the problem considered in each of the two models’ setting can be optimally solved with polynomial time algorithm by reducing to assignment problem. Finally, two examples are provided to illustrate the solution procedures.     

Single-machine due-window assignment scheduling based on common flow allowance,learning effect and resource allocation

This article considers a single-machine due-window assignment scheduling problem based on a common flow allowance (i.e. all jobs have slack due window (SLKW)). We assume that the actual processing time of a job is a function of its position in a sequence (learning effect) and its continuously divisible and non-renewable resource allocation. The problem is to determine the optimal due windows, the optimal resource allocation and the processing sequence simultaneously to minimise costs for earliness, tardiness, the window location, window size, makespan and resource consumption. For a linear or a convex function of the amount of a resource allocated to the job, we provide a polynomial time algorithm, respectively. Some extensions of the problem are also shown.     

Multitasking scheduling problems with a rate-modifying activity

Motivated by the behavioral phenomena that occur while human operators are carrying out tasks, we study multitasking scheduling problems with a rate-modifying activity. In the problems, the processing of a selected task suffers from interruptions by other tasks that are available but unfinished, and the human operators regularly engage rest breaks during work shifts allowing them to recover or mitigate some of the negative effects of fatigue. The objectives are to respectively minimize: makespan, total completion time, maximum lateness, and due-date assignment related cost by determining when to schedule the rate modifying activity and the optimal task sequence in the presence of multitasking. Scheduling models and algorithms are proposed to solve the problems. The numerical examples are presented to illustrate the theorems and algorithms.     

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.     

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.     

Fast and meta-heuristics for common due-date assignment and scheduling on parallel machines

This study considers common due-date assignment and scheduling on parallel machines. The problem has three decision variables: assigning the common-due-date, allocating jobs to parallel machines, and sequencing the jobs assigned to each machine. The objective is to minimise the sum of due-date assignment, earliness and tardiness penalties. A mathematical programming model is presented, and then two types of heuristics are suggested after characterising the optimal solution properties. The two types of heuristics are: (a) a fast two-stage heuristic with obtaining an initial solution and improvement; and (b) two meta-heuristics, tabu search and simulated annealing, with new neighbourhood generation methods. Computational experiments were conducted on a number of test instances, and the results show that each of the heuristic types outperforms the existing one. In particular, the meta-heuristics suggested in this study are significantly better than the existing genetic algorithm.     

Parallel machine scheduling with preference of machines

This paper considers a scheduling problem in the manufacturing of anodic electro-etching aluminium foil. To reduce cost and increase efficiency, the manufacturer of aluminium foil usually designs the equipment for electro-etching of aluminium foil into specialised equipment that is dedicated to produce high voltage or medium voltage aluminium foil based on the range the aluminium foil can bear. Nevertheless, high voltage equipment can be used to produce medium voltage aluminium foil with longer processing time, and vice versa. The problem is to schedule jobs on the high and medium voltage equipment, each having several pieces in parallel, with setup times to minimise to the total completion time. In this paper, we propose a three-stage heuristic for this problem and computationally evaluate the performance of the heuristic in comparison to a heuristic for unrelated parallel machines and a branch-and-bound algorithm.     

A fixed job scheduling problem with machine-dependent job weights

This study considers the identical parallel machines operational fixed job scheduling problem with machine-dependent job weights. A job is either processed in a fixed interval or is not processed at all. Our aim is to maximise the total weight of the processed jobs. We show that the problem with machine eligibility constraints resides as a special case of this problem. We identify some special polynomially solvable cases and propose a branch-and-bound (BB) algorithm that employs efficient bounding schemes and dominance conditions. Computational experience on large-sized problem examples reveals the satisfactory performance of the BB algorithm.     

Single-machine batch delivery scheduling and common due-date assignment with a rate-modifying activity

We consider batch delivery scheduling on a single machine, where a common due-date is assigned to all the jobs and a rate-modifying activity on the machine may be scheduled, which can change the processing rate of the machine. Thus the actual processing time of a job is variable depending on whether it is processed before or after the rate-modifying activity. The objective is to determine the optimal job sequence, the optimal partition of the job sequence into batches, the optimal assigned common due-date, and the optimal location of the rate-modifying activity simultaneously to minimize the total cost of earliness, job holding, weighted number of tardy jobs, due-date assignment, and batch delivery. We derive some structural properties of the problem, based on which we design polynomial-time algorithms to solve some special cases of the problem.     

On scheduling models for the frequency interval assignment problem with cumulative interferences

In this article, models and methods for solving a real-life frequency assignment problem based on scheduling theory are investigated. A realistic frequency assignment problem involving cumulative interference constraints in which the aim is to maximize the number of assigned users is considered. If interferences are assumed to be binary, a multiple carrier frequency assignment problem can be treated as a disjunctive scheduling problem since a user requesting a number of contiguous frequencies can be considered as a non-preemptive task with a processing time, and two interfering users can be modelled through a disjunctive constraint on the corresponding tasks. A binary interference version of the problem is constructed and a disjunctive scheduling model is derived. Based on the binary representation, two models are proposed. The first one relies on an interference matrix and the second one considers maximal cliques. A third, cumulative, model that yields a new class of scheduling problems is also proposed. Computational experiments show that the case-study frequency assignment problem can be solved efficiently with disjunctive scheduling techniques.     

A canned food scheduling problem with batch due date

This article considers a canned food scheduling problem where jobs are grouped into several batches. Jobs can be sent to the next operation only when all the jobs in the same batch have finished their processing, i.e. jobs in a batch, have a common due date. This batch due date problem is quite common in canned food factories, but there is no efficient heuristic to solve the problem. The problem can be formulated as an identical parallel machine problem with batch due date to minimize the total tardiness. Since the problem is NP hard, two heuristics are proposed to find the near-optimal solution. Computational results comparing the effectiveness and efficiency of the two proposed heuristics with an existing heuristic are reported and discussed.     

Due-date assignment and single-machine scheduling with generalised position-dependent deteriorating jobs and deteriorating multi-maintenance activities

This paper addresses a single-machine scheduling problem with simultaneous consideration of due-date assignment, generalised position-dependent deteriorating jobs, and deteriorating maintenance activities. It is assumed that the actual processing time of a job is a general non-decreasing function depending on the number of maintenance activities performed before it and its position in a sequence. Moreover, the machine may be subject to several maintenance activities up to a limit over the scheduling horizon. The maintenance activities do not necessarily restore the machine fully to its original perfect state and the duration of a maintenance activity depends on its start time. The objective is to find jointly the optimal job sequence, maintenance frequency and maintenance positions to minimise an objective function that includes the cost of due-date assignment, the cost of discarding jobs that cannot be completed by their due dates and the earliness of the scheduled jobs under the popular CON and SLK due-date assignment methods. We provide polynomial-time solution algorithms for various versions of the problem.     

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.     

Parallel machine scheduling with tool loading: a constraint programming approach

This paper presents constraint programming models that aim to solve scheduling and tool assignment problems in parallel machine environments. There are a number of jobs to be processed on parallel machines. Each job requires a set of tools, but limited number of tools are available in the system due to economic restrictions. The problem is to assign the jobs and the required tools to machines and to determine the schedule so that the makespan is minimised. Three constraint programming models are developed and compared with existing methods described in the literature.     

Loading and sequencing heuristics for job scheduling on two unrelated parallel machines with long,sequence-dependent set-up times

The purpose of this paper is to develop and test intelligible heuristics for the scheduling of production orders that can easily be used in practice. Grounded in a case study, this paper examines the combined effects of assignment and sequencing heuristics on commonly used performance indicators. Discrete event simulation is used in the analysis to adequately capture the complexity found in the case study: production orders differing in many aspects, two unrelated parallel machines with varying and product-specific speed, and set-up times that depend on the (dis)similarity of successive orders. Evaluating 108 strategy–scenario combinations including the base case derived from the case study, it is found that a loading heuristic based on order quantity and scheduled capacity in combination with the shortest set-up heuristic performs best. When compared to the heuristic approach used by the case company, this strategy saves about 13.9% of total machine busy time and increases service level by 10.2%. In addition, using a reduced set of 40 production orders we are able to demonstrate that the best heuristic strategies comes close to results generated in a two-stage optimisation. The gap to optimality is only 3.1% in total busy time on average over all scenarios.