Single Machine Batching Problem With Pentaties And Release Time

In recent years, with the growing and innovation of science technology and the development of manufacturing. The importance of scheduling problems has been strengthened and has become an important direction of scientific research. Many researchers have done a lot of research for scheduling problem.There are a lot of research direction of scheduling problem, such as Job-Shop Scheduling, single batching machine and parallel batching. In this paper, we mainly study the following single-machine scheduling problem:Given n jobs, of which the properties of each job comprising:processing time pj; release time rj (before this time, the job can not be scheduled); penalty value ej (the job can be rejected, but when refused the job, we must pay a certain price, that is, ej). Given a machine for processing these jobs. The machine can process up to b jobs simultaneously. The jobs processed together form a batch, the processing time of which is the longest processing time of all the jobs in the batch. Therefore, all the jobs in one batch have the same start time and the same completion time. No preemption is permitted. Our goal is to choose jobs for processing, divide these jobs into batches and sequence these batches so that the total completion times of these jobs plus the total penalty of the rejected ones is minimized.