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.     

Integrated production scheduling and vehicle routing problem with job splitting and delivery time windows

In this paper, we study a production scheduling and vehicle routing problem with job splitting and delivery time windows in a company working in the metal packaging industry. In this problem, a set of jobs has to be processed on unrelated parallel machines with job splitting and sequence-dependent setup time (cost). Then the finished products are delivered in batches to several customers with heterogeneous vehicles, subject to delivery time windows. The objective of production is to minimize the total setup cost and the objective of distribution is to minimize the transportation cost. We propose mathematical models for decentralized scheduling problems, where a production schedule and a distribution plan are built consecutively. We develop a two-phase iterative heuristic to solve the integrated scheduling problem. We evaluate the benefits of coordination through numerical experiments.     

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.     

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.     

A method combining rules with genetic algorithm for minimizing makespan on a batch processing machine with preventive maintenance

This paper considers the problem of minimising makespan on a single batch processing machine with flexible periodic preventive maintenance. This problem combines two sub-problems, scheduling on a batch processing machine with jobs’ release dates considered and arranging the preventive maintenance activities on a batch processing machine. The preventive maintenance activities are flexible but the maximum continuous working time of the machine, which is allowed, is determined. A mathematical model for integrating flexible periodic preventive maintenance into batch processing machine problem is proposed, in which the grouping of jobs with incompatible job families, the starting time of batches and the preventive maintenance activities are optimised simultaneously. A method combining rules with the genetic algorithm is proposed to solve this model, in which a batching rule is proposed to group jobs with incompatible job families into batches and a modified genetic algorithm is proposed to schedule batches and arrange preventive maintenance activities. The computational results indicate the method is effective under practical problem sizes. In addition, the influences of jobs’ parameters on the performance of the method are analyzed, such as the number of jobs, the number of job families, jobs’ processing time and jobs’ release time.     

Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes

The paper addresses minimizing makespan by a genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single-batch-processing machine. A batch-processing machine can process up to B jobs simultaneously. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Two different GAs are proposed based on different encoding schemes. The first is a sequence-based GA (SGA) that generates random sequences of jobs using GA operators and applies the batch first fit heuristic to group the jobs. The second is a batch-based hybrid GA (BHGA) that generates random batches of jobs using GA operators and ensures feasibility by using knowledge of the problem based on a heuristic procedure. A greedy local search heuristic based on the problem characteristics is hybridized with a BHGA that has the ability of steering efficiently the search toward the optimal or near-optimal schedules. The performance of proposed GAs is compared with a simulated annealing (SA) approach proposed by Melouk et al. (Melouk, S., Damodaran, P. and Chang, P.Y., Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. Int. J. Prod. Econ., 2004, 87, 141–147) and also against a modified lower bound proposed for the problem. Computational results show that BHGA performs considerably well compared with the modified lower bound and significantly outperforms the SGA and SA in terms of both quality of solutions and required runtimes.     

A bi-objective parallel machine problem with eligibility,release dates and delivery times of the jobs

The scheduling of parallel machines is a well-known problem in many companies. Nevertheless, not always all the jobs can be manufactured in any machine and the eligibility appears. Based on a real-life problem, we present a model which has m parallel machines with different level of quality from the highest level for the first machine till the lowest level for the last machine. The set of jobs to be scheduled on these m parallel machines are also distributed among these m levels: one job from a level can be manufactured in a machine of the same or higher level but a penalty, depending on the level, appears when a job is manufactured in a machine different from the highest level i.e. different from the first machine. Besides, there are release dates and delivery times associated to each job. The tackled problem is bi-objective with the criteria: minimisation of the final date – i.e. the maximum for all the jobs of their completion time plus the delivery time – and the minimisation of the total penalty generated by the jobs. In a first step, we analyse the sub-problem of minimisation of the final date on a single machine for jobs with release dates and delivery times. Four heuristics and an improvement algorithm are proposed and compared on didactic examples and on a large set of instances. In a second step an algorithm is proposed to approximate the set of efficient solutions and the Pareto front of the bi-objective problem. This algorithm contains two phases: the first is a depth search phase and the second is a backtracking phase. The procedure is illustrated in detail on an instance with 20 jobs and 3 machines. Then extensive numerical experiments are realised on two different sets of instances, with 20, 30 and 50 jobs, 3 or 4 machines and various values of penalties. Except for the case of 50 jobs, the results are compared with the exact Pareto front.     

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.     

SINGLE-MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND EARLINESS,TARDINESS AND COMPLETION TIME PENALTIES

The paper considers the problem of scheduling nindependent and simultaneously available jobs on a single machine, where the job processing times are compressible as a linear cost function. The objective is to find an optimal permutation of the jobs, an optimal due date and the optimal processing times which jointly minimize a cost function consisting of the earliness, tardiness, completion time and compressing costs. It shows that the problem can be solved as an assignment problem.     

Heuristic control of multiple batch processors with incompatible job families and future job arrivals

We analyse the problem of minimising the mean cycle time of a batch processing stage containing K?>?1 batch processors in parallel with incompatible job families and future job arrivals. We provide an integer linear programming formulation and a dynamic program formulation for small problem instances. For larger problem instances, we propose an online heuristic policy MPC_REPEAT. At each instance a decision has to be made, MPC_REPEAT decomposes the problem of simultaneously assigning multiple batches to multiple processors into sequentially assigning multiple batches to multiple processors. When job families are uncorrelated, we show via simulation experiments that MPC_REPEAT has significantly lower mean cycle time than a previously proposed look-ahead method except when: (MPC_REPEAT ignores some job families AND the traffic intensity is high.) Our experiments also reveal that increasing the job family correlation of consecutive job arrivals results, with a few exceptions, in a mean cycle-time reduction, for both policies evaluated. This reduction in cycle time generally increases with: increasing number of job families, decreasing number of processors, and increasing time between job arrivals. Our findings imply that controlling the upstream processors, such that job families of consecutive job arrivals are correlated, can reduce the cycle time at the batch processing stage. Furthermore, the expected mean cycle time reduction due to this strategy can be substantially larger than that expected from switching to a more complex batch processing stage policy, under less stringent conditions.     

Production problems with deadline penalties

This paper considers the scheduling problem faced by a manufacturer who is required to conform strictly to previously agreed due dates (or delivery dates), Penalties are assessed in the event that the product or service delivered is not yet complete. The model allows for a disruption cost each time a delivery is made. The objective is to minimize a total penalty function based on the announced due dates, the tardiness of each job and the number of distinct due dates used. The problem is solved by an efficient algorithm which simultaneously finds optimal solutions for the number of due dates to use, the specifications of those due dates and the order of processing for the jobs. A numerical example demonstrates the operation of the algorithm.     

An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times

We consider the problem of scheduling families of jobs in a two-machine open shop so as to minimize the makespan. The jobs of each family can be partitioned into batches and a family setup time on each machine is required before the first job is processed, and when a machine switches from processing a job of some family to a job of another family. For this NP-hard problem the literature contains (5/4)-approximation algorithms that cannot be improved on using the class of group technology algorithms in which each family is kept as a single batch. We demonstrate that there is no advantage in splitting a family more than once. We present an algorithm that splits one family at most once on a machine and delivers a worst-case performance ratio of 6/5.     

Scheduling a no-wait flow shop containing unbounded batching machines

We study the problem of scheduling n jobs in a no-wait flow shop consisting of m batching machines. Each job has to be processed by all the machines. All jobs visit the machines in the same order. A job completed on an upstream machine should be immediately transferred to the downstream machine. Batching machines can process several jobs simultaneously in a batch so that all jobs of the same batch start and complete together. The processing time of a batch is equal to the maximum processing time of the jobs in this batch. We assume that the capacity of any batch is unbounded. The problem is to find an optimal batch schedule such that the maximum job completion time, that is the makespan, is minimized. For m = 2, we prove that there exists an optimal schedule with at most two batches and construct such a schedule in O(n log n) time. For m = 3, we prove that the number of batches can be limited to nine and give an example where all optimal schedules have seven batches. Furthermore, we prove that the best schedules with at most one, two and three batches are 3-, 2- and 3/2-approximate solutions, respectively. The first two bounds are tight for corresponding schedules. Finally, we suggest an assignment method that solves the problem with m machines and at most r batches in O(n^{m(r-2)+1+[m/r]}) time, if m and r are fixed. The method can be generalized to minimize an arbitrary maximum cost or total cost objective function.     

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.     

Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabu search method

This paper investigates an integrated bi-objective optimisation problem with non-resumable jobs for production scheduling and preventive maintenance in a two-stage hybrid flow shop with one machine on the first stage and m identical parallel machines on the second stage. Sequence-dependent set-up times and preventive maintenance (PM) on the first stage machine are considered. The scheduling objectives are to minimise the unavailability of the first stage machine and to minimise the makespan simultaneously. To solve this integrated problem, three decisions have to be made: determine the processing sequence of jobs on the first stage machine, determine whether or not to perform PM activity just after each job, and specify the processing machine of each job on the second stage. Due to the complexity of the problem, a multi-objective tabu search (MOTS) method is adapted with the implementation details. The method generates non-dominated solutions with several parallel tabu lists and Pareto dominance concept. The performance of the method is compared with that of a well-known multi-objective genetic algorithm, in terms of standard multi-objective metrics. Computational results show that the proposed MOTS yields a better approximation.     

Heuristics for permutation flow shop scheduling with batch setup times

In this paper we consider permutation flow shop scheduling problems with batch setup times. Each job has to be processed on each machine once and the technological routes are identical for all jobs. The set of jobs is divided into groups. There are given processing timest _ij of jobi on machinej and setup timess _rj on machinej when a job of ther-th group is processed after a job of another group. It is assumed that the same job order has to be chosen on each machine. We consider both the problems of minimizing the makespan and of minimizing the sum of completion times, where batch or item availability of the jobs is assumed. For these problems we give various constructive and iterative algorithms. The constructive algorithms are based on insertion techniques combined with beam search. We introduce suitable neighbourhood structures for such problems with batch setup times and describe iterative algorithms that are based on local search and reinsertion techniques. The developed algorithms have been tested on a large collection of problems with up to 80 jobs.Supported by Deutsche Forschungsgemeinschaft (Project ScheMA) and by the International Association for the Promotion of Cooperation with Scientists from the Independent States of the Former Soviet Union (Project INTAS-93-257)     

Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions

We consider the following scheduling problem. We are given a set S of jobs which are to be scheduled sequentially on a single processor. Each job has an associated processing time which is required for its processing. Given a particular permutation of the jobs in S, the jobs are processed in that order with each job started as soon as possible, subject only to the following constraint: For a fixed integer \(B \ge 2\), no unit time interval \([x, x+1)\) is allowed to intersect more than B jobs for any real x. There are several real world situations for which this restriction is natural. For example, suppose in addition to the jobs being executed sequentially on a single main processor, each job also requires the use of one of B identical subprocessors during its execution. Each time a job is completed, the subprocessor it was using requires one unit of time to reset itself. In this way, it is never possible for more than B jobs to be worked on during any unit interval. In Braun et al. (J Sched 17: 399–403, 2014a) it is shown that this problem is NP-hard when the value B is variable and a classical worst-case analysis of List Scheduling for this situation has been carried out. We prove a tighter bound for List Scheduling for \(B\ge 3\) and we analyze the worst-case behavior of the makespan \(\tau _\mathrm{LPT}(S)\) of LPT (longest processing time first) schedules (where we rearrange the set S of jobs into non-increasing order) in relation to the makespan \(\tau _o(S)\) of optimal schedules. We show that LPT ordered jobs can be processed within a factor of \(2-2/B\) of the optimum (plus 1) and that this factor is best possible.     

Multi-objective analysis of an integrated supply chain scheduling problem

We study the problem of minimising the total weighted tardiness and total distribution costs in an integrated production and distribution environment. Orders are received by a manufacturer, processed on a single production line, and delivered to customers by capacitated vehicles. Each order (job) is associated with a customer, weight (priority), processing time, due time, and size (volume or storage space required in the transportation unit). A mathematical model is presented in which a number of weighted linear combinations of the objectives are used to aggregate both objectives into a single objective. Because even the single objective problem is NP-hard, different heuristics based on a genetic algorithm (GA) are developed to further approximate a Pareto-optimal set of solutions for our multi-objective problem.