Single machine batch scheduling with sequential job processing

The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both the bounded and unbounded problems in which all due dates and/or processing times are equal. Several special cases of the bounded problem are shown to be NP-hard. Thus, a comprehensive classification of the computational complexities of the special cases is provided.     

Scheduling with generalized batch delivery dates and earliness penalties

In this paper, we study some single machine scheduling problems with generalized batch delivery dates and earliness penalties. The generalized delivery dates are given a-priori before any jobs are processed. They are unrelated to the jobs and the processing order. Each specific delivery batch contains jobs completed but undelivered until the specific delivery date. We consider scheduling problems to minimize two types of earliness penalties: one is the total earliness; the other is the maximum earliness. For these two problems, first we show that they are NP-hard in the strong sense for general cases; then we prove that they are still NP-hard even if there are only two generalized batch dates. We also prove that they are solved in polynomial time for general earliness penalty function if all processing times are equal, and give an O(n log(n)) algorithm to solve the weighted earliness cases.     

Probabilistic asymptotic analysis of stochastic online scheduling problems

In the stochastic online scheduling environment, jobs with unknown release times and weights arrive over time. Upon arrival, the information on the weight of the job is revealed but the processing requirement remains unknown until the job is finished. In this paper we consider the objective of minimizing the total weighted completion time. With the assumptions that job weights are bounded, machine capacity is adequate, and processing requirements are bounded and identical and independently distributed across the machines and jobs, we show that any nondelay algorithm is asymptotically optimal for the stochastic online single machine problem, flow shop problem, and uniform parallel machine problem. Our simulation studies of these stochastic online scheduling problems show that two generic nondelay algorithms perform very well as long as the number of jobs is larger than 100.     

On bilevel machine scheduling problems

Bilevel scheduling problems constitute a hardly studied area of scheduling theory. In this paper, we summarise the basic concepts of bilevel optimisation, and discuss two problem classes for which we establish various complexity and algorithmic results. The first one is the bilevel total weighted completion time problem in which the leader assigns the jobs to parallel machines and the follower sequences the jobs assigned to each machine. Both the leader and the follower aims to minimise the total weighted completion time objective, but with different job weights. When the leader’s weights are arbitrary, the problem is NP-hard. However, when all the jobs are of unit weight for the leader, we provide a heuristic algorithm based on iterative LP-rounding along with computational results, and provide a sufficient condition when the LP-solution is integral. In addition, if the follower weights induce a monotone (increasing or decreasing) processing time order in any optimal solution, the problem becomes polynomially solvable. As a by-product, we characterise a new polynomially solvable special case of the MAX m-CUT problem, and provide a new linear programming formulation for the P||?_j C_j{P||\sum_j C_j} problem. Finally, we present some results on the bilevel order acceptance problem, where the leader decides on the acceptance of orders and the follower sequences the jobs. Each job has a deadline and if a job is accepted, it cannot be late. The leader’s objective is to maximise the total weight of accepted jobs, whereas the follower aims at minimising the total weighted job completion times. For this problem, we generalise some known single-level machine scheduling algorithms.     

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.     

Scheduling a batch processing machine with non-identical job sizes

The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with arbitrary job processing times, job weights and job sizes. The scheduling objective is to minimize total weighted completion time. We find that the procedure returns optimal solutions to problems of up to 25 jobs in reasonable CPU time, and can be adapted for use as a heuristic for larger problems.     

A hybrid VNS-HS algorithm for a supply chain scheduling problem with deteriorating jobs

This paper investigates a coordinated scheduling problem in a two stage supply chain where parallel-batching machine, deteriorating jobs and transportation coordination are considered simultaneously. During the production stage, jobs are processed by suppliers and there exists one parallel-batching machine in each supplier. The actual processing time of a job depends on its starting time and normal processing time. The normal processing time of a batch is equal to the largest normal processing time among all jobs in its batch. During the transportation stage, the jobs are then delivered to the manufacturer. Since suppliers are distributed in different locations, the transportation time between each supplier and the manufacturer is different. Based on some structural properties of the studied problem, an optimal algorithm for minimising makespan on a single supplier is presented. This supply chain scheduling problem is proved to be NP-hard, and a hybrid VNS-HS algorithm combining variable neighbourhood search (VNS) with harmony search (HS) is proposed to find a good solution in reasonable time. Finally, some computational experiments are conducted and the results demonstrate the effectiveness and efficiency of the proposed VNS-HS.     

Production in the factory of the future

This paper proposes an algorithm for hoist scheduling problems in a flexible PCB electroplating line where there is no buffer among workstations. Due to its chemical process nature, the processing times have to be controlled within a specified range (i.e. between a maximum processing time and a minimum processing time). The product will become defective if this constant is violated. The objective is to maximize throughput with no defective product. The proposed algorithm schedules jobs entering the system based on the specified range of processing time. A simulation study shows that the proposed algorithm outperforms the basic algorithm that schedules jobs based on the minimum processing times.     

Scheduling and co-ordination of multi-suppliers single-warehouse-operator single-manufacturer supply chains with variable production rates and storage costs

We study a supply chain scheduling and co-ordination problem comprising multiple suppliers, a single warehouse operator, a single manufacturer, and multiple retailers, where the supply chain has limited production capacity that can take only some of the orders from the retailers. For a decentralised supply chain, the manufacturer is a decision maker that selects the orders and aims to maximise its own profit, where the profit is a function of the order storage time and storage quantity, order sequence-dependent weighted storage costs, and idle time of the orders. On the other hand, for a centralised supply chain, a supply chain co-ordinator exists that aims to maximise the profit of the whole supply chain and allocates the profit among the supply chain members. We first formulate the problem as a two-machine common-due-window flow shop scheduling problem. We then develop a theorem and two algorithms to solve the optimal scheduling problems in both the decentralised and centralised supply chains. With these results, we develop a method that can achieve channel co-ordination based on a profit sharing rule, together with an increase in the production rates and a decrease in the storage costs.     

Integrated production scheduling and batch delivery with fixed departure times and inventory holding costs

In this paper, we address a model for supply chain coordination. There are m manufacturers modelled as single machines, each of which processes a specific set of jobs (products). After processing is completed, jobs are batched, and batches are shipped to a customer by means of vehicles. The problem consists in concurrently finding a production schedule of the jobs, a partition of jobs into delivery batches and an assignment of delivery batches to vehicles, so that jobs are delivered within their deadlines and total costs are minimised. We focus on a scenario characterised by fixed departure times and inventory holding costs. For each departure time there is a given number of vehicles, possibly having limited capacity. Each job incurs a cost proportional to the time from job completion to delivery departure. In this paper, we show that the problem is NP-hard even for a very restricted case, and report various polynomiality results for two scenarios, namely: (i) when the production sequence of each manufacturer is fixed in advance, and (ii) when there is a single manufacturer and processing times are all equal to 1. We also point out several open problems.     

Modelling and symmetry breaking in scheduling problems on batch processing machines

Problems of scheduling batch-processing machines to minimise the makespan are widely exploited in the literature, mainly motivated by real-world applications, such as burn-in tests in the semiconductor industry. These problems consist of grouping jobs in batches and scheduling them on machines. We consider problems where jobs have non-identical sizes and processing times, and the total size of each batch cannot exceed the machine capacity. The processing time of a batch is defined as the longest processing time among all jobs assigned to it. Jobs can also have non-identical release times, and in this case, a batch can only be processed when all jobs assigned to it are available. This paper discusses four different versions of batch scheduling problems, considering a single processing machine or parallel processing machines and considering jobs with or without release times. New mixed integer linear programming formulations are proposed as enhancements of formulations proposed in the literature, and symmetry breaking constraints are investigated to reduce the size of the feasible sets. Computational results show that the proposed formulations have a better performance than other models in the literature, being able to solve to optimality instances only considered before to be solved by heuristic procedures.     

β-Robust scheduling for single-machine systems with uncertain processing times

In scheduling environments with processing time uncertainty, system performance is determined by both the sequence in which jobs are ordered and the actual processing times of jobs. For these situations, the risk of achieving substandard system performance can be an important measure of scheduling effectiveness. To hedge this risk requires an explicit consideration of both the mean and the variance of system performance associated with alternative schedules, and motivates a β-robustness objective to capture the likelihood that a schedule yields actual performance no worse than a given target level. In this paper we focus on β-robust scheduling issues in single-stage production environments with uncertain processing times. We define a general β-robust scheduling objective, formulate the β-robust scheduling problem that results when job processing times are independent random variables and the performance measure of interest is the total flow time across all jobs, establish problem complexity, and develop exact and heuristic solution approaches. We then extend the 0-robust scheduling model to consider situations where the uncertainty associated with individual job processing times can be selectively controlled through resource allocation. Computational results are reported to demonstrate the efficiency and effectiveness of the solution procedures.     

Sensitivity analysis of a fuzzy multiobjective scheduling problem

This paper concerns sensitivity analysis of a class of complex job shop scheduling problems which are characterized by: (1) a large number of jobs and machines, (2) uncertain jobs processing times, and (3) multiple measures of schedule performance including average weighted tardiness, the number of tardy jobs, the total setup times, the total idle time of machines, and the total flow times of jobs. The base schedule is generated by applying a new fuzzy multiobjective genetic algorithm which takes into consideration batching of the jobs of a similar type, jobs’ lots sizing and load balancing of the machines. The aim of the proposed sensitivity analysis of a generated schedule is to investigate the consequences of prolongations of job processing times on the measures of schedule performance. The processing times are described by triangular fuzzy numbers and their prolongation is done by expanding the supports of fuzzy numbers. The sensitivity analysis is performed through a series of numerical experiments. The effects of prolongations of job processing times on the measures of performance of a generated schedule are recorded and analysed. It is shown that the sensitivity analysis is among the primaries in evaluating the quality of a generated schedule. The sensitivity analysis is used in identifying the critical jobs and the critical machines which have the properties that the prolongations of their processing times produce the largest deteriorations of the performance measures and the overall quality of a generated schedule.     

Scheduling preventive maintenance on a single CNC machine

In this study we attempt to deal with process planning, scheduling and preventive maintenance (PM) decisions, simultaneously. The objective is to minimize the total completion time of a set of jobs on a CNC machine. During the process planning, we decide on the processing times of the jobs which are controllable (i.e. they can be easily changed) on CNC machines. Using shorter processing times (higher production rates) would result in greater deterioration of the machine, and we would need to plan more frequent PM visits to the machine, during which it would not be available. Therefore, the selected processing times determine not only the completion times but also the PM visit times. We first provide optimality properties for the joint problem. We propose a new heuristic search algorithm to determine simultaneously the processing times of the jobs, their sequence and the PM schedule.     

Scheduling with controllable processing times and compression costs using population-based heuristics

This paper considers the single machine scheduling problem of jobs with controllable processing times and compression costs and the objective to minimise the total weighted job completion time plus the cost of compression. The problem is known to be intractable, and therefore it was decided to be tackled by population-based heuristics namely differential evolution (DE), particle swarm optimisation (PSO), genetic algorithms (GAs), and evolution strategies (ES). Population-based heuristics have found wide application in most areas of production research including scheduling theory. It is therefore surprising that this problem has not yet received any attention from the corresponding heuristic algorithms community. This work aims at contributing to fill this gap. An appropriate problem representation scheme is developed together with a multi-objective procedure to quantify the trade-off between the total weighted job completion time and the cost of compression. The four heuristics are evaluated and compared over a large set of test instances ranging from five to 200 jobs. The experiments showed that a differential evolution algorithm is superior (with regard to the quality of the solutions obtained) and faster (with regard to the speed of convergence) to the other approaches.     

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.     

Permutation flow-shop scheduling problem to optimize a quadratic objective function

A flow-shop scheduling model enables appropriate sequencing for each job and for processing on a set of machines in compliance with identical processing orders. The objective is to achieve a feasible schedule for optimizing a given criterion. Permutation is a special setting of the model in which the processing order of the jobs on the machines is identical for each subsequent step of processing. This article addresses the permutation flow-shop scheduling problem to minimize the criterion of total weighted quadratic completion time. With a probability hypothesis, the asymptotic optimality of the weighted shortest processing time schedule under a consistency condition (WSPT-CC) is proven for sufficiently large-scale problems. However, the worst case performance ratio of the WSPT-CC schedule is the square of the number of machines in certain situations. A discrete differential evolution algorithm, where a new crossover method with multiple-point insertion is used to improve the final outcome, is presented to obtain high-quality solutions for moderate-scale problems. A sequence-independent lower bound is designed for pruning in a branch-and-bound algorithm for small-scale problems. A set of random experiments demonstrates the performance of the lower bound and the effectiveness of the proposed algorithms.     

Robust scheduling of a two-machine flow shop with uncertain processing times

This paper focuses on manufacturing environments where job processing times are uncertain. In these settings, scheduling decision makers are exposed to the risk that an optimal schedule with respect to a deterministic or stochastic model will perform poorly when evaluated relative to actual processing times. Since the quality of scheduling decisions is frequently judged as if processing times were known a priori, robust scheduling, i.e., determining a schedule whose performance (compared to the associated optimal schedule) is relatively insensitive to the potential realizations of job processing times, provides a reasonable mechanism for hedging against the prevailing processing time uncertainty. In this paper we focus on a two-machine flow shop environment in which the processing times of jobs are uncertain and the performance measure of interest is system makespan. We present a measure of schedule robustness that explicitly considers the risk of poor system performance over all potential realizations of job processing times. We discuss two alternative frameworks for structuring processing time uncertainty. For each case, we define the robust scheduling problem, establish problem complexity, discuss properties of robust schedules, and develop exact and heuristic solution approaches. Computational results indicate that robust schedules provide effective hedges against processing time uncertainty while maintaining excellent expected makespan performance     

Spread time considerations in operational fixed job scheduling

In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.     

单台机器排序问题关于加工时间的反问题

本文研究单台机器总完工时间排序问题关于加工时间的反问题,研究尽量"小"地调整工件的加工时间使给定工件的加工次序成为最优的排序。我们考虑尽量"小"地调整是分别使最大带权相对离差的绝对值为最小、使总的带权相对离差的绝对值为最小或者使总的带权相对离差的平方为最小等三种情况。通过把问题转化成数学规划,我们分别指出这三种情况下的三个反问题都可以在多项式时间内求解。