به حداقل رساندن زمان اتمام کل در مسائل برنامه ریزی جریا در دو دستگاه جریان کارگاهی دو ماشینه همراه با توالی توالی ثابت کارگاهی

jobs in a two-machine flow shop to minimize the total completion time, subject to the condition that the jobs are processed in the same given sequence on both machines. A new concept of optimal schedule block is introduced, and polynomial time dynamic programming algorithms employing this concept are derived for two specific problems. In the first problem, the machine-2 processing time of a job is a step increasing function of its waiting time between the machines, and a decision about machine-1 idle time insertion has to be made. This problem is solved in O(n2)

This paper studies two scheduling problems in a two-machine flow shop, subject to the condition that the jobs are processed in the same fixed sequence on both machines. A new block approach is proposed and deployed to determine their solutions in polynomial time within the general dynamic programming framework. 1.1. State of the art In machine scheduling, a schedule specifies job starting and completion times on the machines. In some cases, it is completely characterized by the job sequence, and in the other cases, extra information is needed to fully specify it. A complicated schedule structure is typical for two major types of scheduling: scheduling with inserted machine idle time [1] and batch scheduling [2]. A commonly used approach to tackle NP-hard problems of these types is to derive an optimal polynomial time algorithm for the problem in which jobs are processed in the same fixed sequence. Then this algorithm can be used in a local search method to evaluate candidate job sequences for the general problem. There also exist studies, in which a specific optimal job sequence is established analytically. In real-life applications, a job sequence can be given as an input data of the problem. Shafransky and Strusevich [3] studied several open shop scheduling problems, subject to a given sequence of jobs on one machine, and mentioned that a pre-assigned sequence of jobs could be retained on one of the machines in the manufacturing process owing to technological or managerial decisions. A fixed job sequence can also appear due to the application of the First-Come–First-Served principle, which is commonly regarded fair by customers.

This paper studies two scheduling problems in a two-machine flow shop, subject to the condition that the jobs are processed in the same fixed sequence on both machines. A new block approach is proposed and deployed to determine their solutions in polynomial time within the general dynamic programming framework. 1.1. State of the art In machine scheduling, a schedule specifies job starting and completion times on the machines. In some cases, it is completely characterized by the job sequence, and in the other cases, extra information is needed to fully specify it. A complicated schedule structure is typical for two major types of scheduling: scheduling with inserted machine idle time [1] and batch scheduling [2]. A commonly used approach to tackle NP-hard problems of these types is to derive an optimal polynomial time algorithm for the problem in which jobs are processed in the same fixed sequence. Then this algorithm can be used in a local search method to evaluate candidate job sequences for the general problem. There also exist studies, in which a specific optimal job sequence is established analytically. In real-life applications, a job sequence can be given as an input data of the problem. Shafransky and Strusevich [3] studied several open shop scheduling problems, subject to a given sequence of jobs on one machine, and mentioned that a pre-assigned sequence of jobs could be retained on one of the machines in the manufacturing process owing to technological or managerial decisions. A fixed job sequence can also appear due to the application of the First-Come–First-Served principle, which is commonly regarded fair by customers.