Common due date assignment and scheduling with a rate-modifying activity to minimize the due date,earliness, tardiness,holding, and batch delivery cost

e consider a single-machine batch delivery scheduling and common due date assignment problem. In addition to making decisions on sequencing the jobs, determining the common due date, and scheduling job delivery, we consider the option of performing a rate-modifying activity on the machine. The processing time of a job scheduled after the rate-modifying activity decreases depending on a job-dependent factor. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a common due date for all the jobs, a location of the rate-modifying activity, and a delivery date for each job to minimize the sum of earliness, tardiness, holding, due date, and delivery cost. We provide some properties of the optimal schedule for the problem and present polynomial algorithms for some special cases.     

Single-machine batch delivery scheduling with an assignable common due date and controllable processing times

We consider single-machine batch delivery scheduling with an assignable common due date and controllable processing times, which vary as a convex function of the amounts of a continuously divisible common resource allocated to individual jobs. Finished jobs are delivered in batches and there is no capacity limit on each delivery batch. We first provide an O(n⁵) dynamic programming algorithm to find the optimal job sequence, the partition of the job sequence into batches, the assigned common due date, and the resource allocation that minimize a cost function based on earliness, tardiness, job holding, due date assignment, batch delivery, and resource consumption. We show that a special case of the problem can be solved by a lower-order polynomial algorithm. We then study the problem of finding the optimal solution to minimize the total cost of earliness, tardiness, job holding, and due date assignment, subject to limited resource availability, and develop an O(nlog n) algorithm to solve it.     

Approximation algorithms for minimizing the total weighted number of late jobs with late deliveries in two-level supply chains

We study a supply chain scheduling problem in which n jobs have to be scheduled on a single machine and delivered to m customers in batches. Each job has a due date, a processing time and a lateness penalty (weight). To save batch-delivery costs, several jobs for the same customer can be delivered together in a batch, including late jobs. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time has to be added before processing the first job in each batch. The objective is to find a schedule which minimizes the sum of the weighted number of late jobs and the delivery costs. We present a pseudo-polynomial algorithm for a restricted case, where late jobs are delivered separately, and show that it becomes polynomial for the special cases when jobs have equal weights and equal delivery costs or equal processing times and equal setup times. We convert the algorithm into an FPTAS and prove that the solution produced by it is near-optimal for the original general problem by performing a parametric analysis of its performance ratio.     

Machine scheduling with job class setup and delivery considerations

We study machine scheduling problems in which the jobs belong to different job classes and they need to be delivered to customers after processing. A setup time is required for a job if it is the first job to be processed on a machine or its processing on a machine follows a job that belongs to another class. Processed jobs are delivered in batches to their respective customers. The batch size is limited by the capacity of the delivery vehicles and each shipment incurs a transport cost and takes a fixed amount of time. The objective is to minimize the weighted sum of the last arrival time of jobs to customers and the delivery (transportation) cost. For the problem of processing jobs on a single machine and delivering them to multiple customers, we develop a dynamic programming algorithm to solve the problem optimally. For the problem of processing jobs on parallel machines and delivering them to a single customer, we propose a heuristic and analyze its performance bound.     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

Unbounded parallel-batch scheduling with family jobs and delivery coordination

We study a scheduling problem that integrates parallel-batch production with family jobs and job delivery at the same time. The jobs are first processed on an unbounded parallel-batch machine and then delivered in batches to their specified customers by a transportation vehicle. We assume that jobs from different families (customers) cannot be processed together by the batch machine and also transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We first show that the problem is NP-hard, and then propose for it a heuristic algorithm with a worst-case performance ratio of 3/2.     

A branch-and-bound algorithm for single-machine scheduling with batch delivery and job release times

This paper addresses scheduling a set of jobs with specified release times on a single machine for delivery in batches to customers or to other machines for further processing. This problem is a natural extension of minimizing the sum of flow times in the presence of release time by considering the possibility of delivering jobs in batches and introducing batch delivery costs. The scheduling objective adopted is that of minimizing the sum of flow times and delivery costs. The extended problem arises in the context of coordination between machine scheduling and a distribution system in a supply chain network. Structural properties of the problem are investigated and used to devise a branch-and-bound solution scheme. Computational experiments show significant improvement over an existing dynamic programming algorithm.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

Using genetic algorithm for lot sizing and scheduling problem with arbitrary job volumes and distinct job due date considerations

This paper considers an integrated lot sizing and scheduling problem for a production–distribution environment with arbitrary job volumes and distinct due dates considerations. In the problem, jobs are firstly batch processed on a batching machine at production stage and then delivered to a pre-specified customer at the subsequent delivery stage by a capacitated vehicle. Each job is associated with a distinct due date and a distinct volume, and has to be delivered to the customer before its due date, i.e. delay is not allowed. The processing time of a batch is a constant independent of the jobs it contains. In production, a constant set-up time as well as a constant set-up cost is required before the first job of this batch is processed. In delivery, a constant delivery time as well as a constant delivery cost is needed for each round-trip delivery between the factory and the customer. Moreover, it is supposed that a job that arrives at the customer before its due date will incur a customer inventory cost. The objective is to find a coordinated lot sizing and scheduling scheme such that the total cost is minimised while guaranteeing a certain customer service level. A mixed integer formulation is proposed for this problem, and then a genetic algorithm is developed to solve it. To evaluate the performance of the proposed genetic algorithm, a lower bound on the objective value is established. Computational experiments show that the proposed genetic algorithm performs well on randomly generated problem instances.     

Earliness–tardiness minimization on scheduling a batch processing machine with non-identical job sizes

This paper considers the scheduling problem of minimizing earliness–tardiness (E/T) on a single batch processing machine with a common due date. The problem is extended to the environment of non-identical job sizes. First, a mathematical model is formulated, which is tested effectively under IBM ILOG CPLEX using the constraint programming solver. Then several optimal properties are given to schedule batches effectively, and by introducing the concept of ARB (Attribute Ratio of Batch), it is proven that the ARB of each batch should be made as small as possible in order to minimize the objective, designed as the heuristic information for assigning jobs into batches. Based on these properties, a heuristic algorithm MARB (Minimum Attribute Ratio of Batch) for batch forming is proposed, and a hybrid genetic algorithm is developed for the problem under study by combining GA (genetic algorithm) with MARB. Experimental results demonstrate that the proposed algorithm outperforms other algorithms in the literature, both for small and large problem instances.     

Scheduling of parallel machines with sequence-dependent batches and product incompatibilities in an automotive glass facility

This application is motivated by a complex real-world scheduling problem found in the bottleneck workstation of the production line of an automotive safety glass manufacturing facility. The scheduling problem consists of scheduling jobs (glass parts) on a number of parallel batch processing machines (furnaces), assigning each job to a batch, and sequencing the batches on each machine. The two main objectives are to maximize the utilization of the parallel machines and to minimize the delay in the completion date of each job in relation to a required due date (specific for each job). Aside from the main objectives, the output batches should also produce a balanced workload on the parallel machines, balanced job due dates within each batch, and minimal capacity loss in the batches. The scheduling problem also considers a batch capacity constraint, sequence-dependent processing times, incompatible product families, additional resources, and machine capability. We propose a two-phase heuristic approach that combines exact methods with search heuristics. The first phase comprises a four-stage mixed-integer linear program for building the batches; the second phase is based on a Greedy Randomized Adaptive Search Procedure for sequencing the batches assigned to each machine. We conducted experiments on instances with up to 100 jobs built with real data from the manufacturing facility. The results are encouraging both in terms of computing time—5 min in average—and quality of the solutions—less than 10 % relative gap from the optimal solution in the first phase and less than 5 % in the second phase. Additional experiments were conducted on randomly generated instances of small, medium, and large size.     

Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities

We study the problem of scheduling on parallel batch processing machines with different capacities under a fuzzy environment to minimize the makespan. The jobs have non-identical sizes and fuzzy processing times. After constructing a mathematical model of the problem, we propose a fuzzy ant colony optimization (FACO) algorithm. Based on the machine capacity constraint, two candidate job lists are adopted to select the jobs for building the batches. Moreover, based on the unoccupied space of the solution, heuristic information is designed for each candidate list to guide the ants. In addition, a fuzzy local optimization algorithm is incorporated to improve the solution quality. Finally, the proposed algorithm is compared with several state-of-the-art algorithms through extensive simulated experiments and statistical tests. The comparative results indicate that the proposed algorithm can find better solutions within reasonable time than all the other compared algorithms.     

Single machine scheduling with delivery dates and cumulative payoffs

We address a single machine scheduling problem with a new optimization criterion and unequal release dates. This new criterion results from a practical situation in the domain of book digitization. Given a set of job-independent delivery dates, the goal is to maximize the cumulative number of jobs processed before each delivery date. We establish the complexity of the general problem. In addition, we discuss some polynomial cases and provide a pseudopolynomial time algorithm for the two-delivery-dates problem based on dynamic programming and some dominance properties. Experimental results are also reported.     

Minimizing maximum tardiness and delivery costs in a batched delivery system

High delivery costs usually urge manufacturers to dispatch their jobs in batches. However, dispatching the jobs in batches can have profound negative effects on important scheduling objective functions such as minimizing maximum tardiness. This paper considers a single machine scheduling problem with the aim of minimizing the maximum tardiness and delivery costs in a single-machine scheduling problem with batched delivery system. A mathematical model is developed for this problem which can serve to solve it with the help of a commercial solver. However, due to the fact that this model happens to be a mixed integer nonlinear programming model the solver cannot guarantee to reach the global solution. For this reason, a branch and bound algorithm (B&B) is presented to obtain the global solution. Besides, a heuristic algorithm for calculation of the initial upper bound is introduced. Computational results show that the algorithm can be beneficial for solving this problem, especially for large size instances.     

A hybrid local search algorithm for scheduling real-world job shops with batch-wise pending due dates

This paper aims at solving a real-world job shop scheduling problem with two characteristics, i.e., the existence of pending due dates and job batches. Due date quotation is an important decision process for contemporary companies that adopt the MTO (make to order) strategy. Although the assignment of due dates is usually performed separately with production scheduling, there exist strong interactions between the two tasks. Therefore, we integrate these two decisions into one optimization model. Meanwhile, each order placed by the customer defines a batch of jobs, for which the same due date should be set. Thus, the completion times of these jobs should be close to one another in order to reduce waiting time and cost. For this purpose, we propose a dispatching rule to synchronize their manufacturing progresses. A two-stage local search algorithm based on the PMBGA (probabilistic model-building genetic algorithm) and parameter perturbation is proposed to solve the integrated scheduling problem and its superiority is revealed by the applications to a real-world mechanical factory.     

Scheduling jobs on a single serial-batching machine with dynamic job arrivals and multiple job types

This paper investigates a scheduling model with certain co-existing features of serial-batching, dynamic job arrival, multi-types of job, and setup time. In this proposed model, the jobs of all types are first partitioned into serial batches, which are then processed on a single serial-batching machine with an independent constant setup time for each new batch. In order to solve this scheduling problem, we divide it into two phases based on job arrival times, and we also derive and prove certain constructive properties for these two phases. Relying on these properties, we develop a two-phase hybrid algorithm (TPHA). In addition, a valid lower bound of the problem is also derived. This is used to validate the quality of the proposed algorithm. Computational experiments, both with small- and large-scale problems, are performed in order to evaluate the performance of TPHA. The computational results indicate that TPHA outperforms seven other heuristic algorithms. For all test problems of different job sizes, the average gap percentage between the makespan, obtained using TPHA, and the lower bound does not exceed 5.41 %.     

An improved approximation algorithm for single machine scheduling with job delivery

In single machine scheduling with release times and job delivery, jobs are processed on a single machine and then delivered by a capacitated vehicle to a single customer. Only one vehicle is employed to deliver these jobs. The vehicle can deliver at most c jobs in a shipment. The delivery completion time of a job is defined as the time in which the delivery batch containing the job is delivered to the customer and the vehicle returns to the machine. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. We provide an approximation algorithm for this problem which is better than that given in the literature, improving the performance ratio from 5/3 to 3/2.     

Scheduling a batching machine with convex resource consumption functions

In various industries jobs undergo a batching, or burn in, process where different tasks are grouped into batches and processed simultaneously. The processing time of each batch is equal to the longest processing time among all jobs contained in the batch. All to date studies dealing with batching machines have considered fixed job processing times. However, in many real life applications job processing times are controllable through the allocation of a limited resource. The most common and realistic model assumes that there exists a non-linear and convex relationship between the amount of resource allocated to a job and its processing time. The scheduler?s task when dealing with controllable processing times is twofold. In addition to solving the sequencing problem, one must establish an optimal resource allocation policy. We combine these two widespread models on a single machine setting, showing that both the makespan and total completion time criteria can be solved in polynomial time. We then show that our proposed approach can be applied to general bi-criteria objective comprising of the makespan and the total completion time.     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.     

Complexity results for an integrated single machine scheduling and outbound delivery problem with fixed sequence

In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine, and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time, and transportation times between customers are taken into account. Because the sequence is given, the problem consists in forming batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NP-hardness of the general problem is established, and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NP-hardness proofs and polynomial time algorithms are given. Finally, a fixed-parameter tractability result is given.