Minimizing makespan in an ordered flow shop with?machine-dependent processing times

We consider a generalization of the proportionate flow shop problem with the makespan objective. Each job has a processing requirement and each machine has a characteristic value. In our case, we assume that the time a job occupies a machine is equal to the processing requirement of the job plus a setup time that is equal to the characteristic value of that machine. In this paper, we consider permutation schedules and show that the problem is solvable in polynomial time when the number of machines is fixed.     

Two-stage proportionate flexible flow shop to minimize the makespan

We consider a two-stage flexible flow shop problem with a single machine at one stage and m identical machines at the other stage, where the processing times of each job at both stages are identical. The objective is to minimize the makespan. We describe some optimality conditions and show that the problem is NP-hard when m is fixed. Finally, we present an approximation algorithm that has a worst-case performance ratio of $\frac{5}{4}$ for m=2 and $\frac{\sqrt{1+m^{2}}+1+m}{2m}$ for m≥3.     

Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty

We consider a single-machine scheduling problem such that the due dates are assigned to each job depending on its order, and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total penalty for the earliness and tardiness of each job. The early penalty proportionally increases according to the earliness amount, while the tardy penalty increases according to the step function. We show that the problem is strongly NP-hard, and furthermore, polynomially solvable if the two types of processing times exist.