A Note on DP Algorithm for Batching Scheduling to Minimize Maximum Lateness

In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n^2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.

A Cooperated Imperialist Competitive Algorithm for Unrelated Parallel Batch Machine Scheduling Problem

This study focuses on the scheduling problem of unrelated parallel batch processing machines(BPM)with release times,a scenario derived from the moulding process in a foundry.In this process,a batch is initially formed,placed in a sandbox,and then the sandbox is positioned on a BPM formoulding.The complexity of the scheduling problem increases due to the consideration of BPM capacity and sandbox volume.To minimize the makespan,a new cooperated imperialist competitive algorithm(CICA)is introduced.In CICA,the number of empires is not a parameter,and four empires aremaintained throughout the search process.Two types of assimilations are achieved:The strongest and weakest empires cooperate in their assimilation,while the remaining two empires,having a close normalization total cost,combine in their assimilation.A new form of imperialist competition is proposed to prevent insufficient competition,and the unique features of the problem are effectively utilized.Computational experiments are conducted across several instances,and a significant amount of experimental results show that the newstrategies of CICAare effective,indicating promising advantages for the considered BPMscheduling problems.

An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches

In order to solve the flexible job shop scheduling problem with variable batches,we propose an improved multiobjective optimization algorithm,which combines the idea of inverse scheduling.First,a flexible job shop problem with the variable batches scheduling model is formulated.Second,we propose a batch optimization algorithm with inverse scheduling in which the batch size is adjusted by the dynamic feedback batch adjusting method.Moreover,in order to increase the diversity of the population,two methods are developed.One is the threshold to control the neighborhood updating,and the other is the dynamic clustering algorithm to update the population.Finally,a group of experiments are carried out.The results show that the improved multi-objective optimization algorithm can ensure the diversity of Pareto solutions effectively,and has effective performance in solving the flexible job shop scheduling problem with variable batches.

Genetic algorithm for short-term scheduling of make-and-pack batch production process

This paper considers a scheduling problem in industrial make-and-pack batch production process. This process equips with sequence-dependent changeover time, multipurpose storage units with limited capacity, storage time, batch splitting, partial equipment connectivity and transfer time. The objective is to make a production plan to satisfy all constraints while meeting demand requirement of packed products from various product families. This problem is NP-hard and the problem size is exponentially large for a realistic-sized problem. Therefore,we propose a genetic algorithm to handle this problem. Solutions to the problems are represented by chromosomes of product family sequences. These sequences are decoded to assign the resource for producing packed products according to forward assignment strategy and resource selection rules. These techniques greatly reduce unnecessary search space and improve search speed. In addition, design of experiment is carefully utilized to determine appropriate parameter settings. Ant colony optimization and Tabu search are also implemented for comparison. At the end of each heuristics, local search is applied for the packed product sequence to improve makespan. In an experimental analysis, all heuristics show the capability to solve large instances within reasonable computational time. In all problem instances, genetic algorithm averagely outperforms ant colony optimization and Tabu search with slightly longer computational time.

Batch Scheduling with Job Processing Time Compatibility and Rejection on a Single

We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine.The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint.Three problems are considered:(1)minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;(2)minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;(3)minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs.We provide an O(n2)time algorithm for the first problem.Moreover,for the other two problems,we first show that they are NP-hard,and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them,respectively.

Modeling and Solving Lot-Splitting Scheduling Problem Based on Process

In flexible job-shop batch scheduling problem, the optimal lot-size of different process is not always the same because of different processing time and set-up time. Even for the same process of the same workpiece, the choice of machine also affects the optimal lot-size. In addition, different choices of lot-size between the constrained processes will impact the manufacture efficiency. Considering that each process has its own appropriate lot-size, we put forward the concept of scheduling with lot-splitting based on process and set up the scheduling model of lot-splitting to critical path process as the core. The model could update the set of batch process and machine selection strategy dynamically to determine processing route and arrange proper lot-size for different processes, to achieve the purpose of optimizing the makespan and reducing the processing batches effectively. The experiment results show that, comparing with lot-splitting scheduling scheme based on workpiece, this model optimizes the makespan and improves the utilization efficiency of the machine. It also greatly decreases the machined batches （42%） and reduces the complexity of shop scheduling production management.

Batch Scheduling with Deteriorating Jobs to Minimize the Total Completion Time

We consider bounded parallel-batch scheduling with proportional-linear deteriorating jobs and the objective to minimize the total completion time.We give some properties of optimal schedules for the problem and present for it a dynamic programming algorithm running in O(b^(2)m^(2)2^(m))time,where b is the size of a batch and m is the number of distinct deterioration rates.