| Summary: | In practical problems, in addition to the processing time of the job, the impact of the time required for delivering the service to customers on the cost is also considered, i.e., delivery time, where the job processing time is a simple linear function of its starting time. This paper considers the impact of past-sequence-dependent delivery times (which can be referred to as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>p</mi><mi>s</mi><mi>d</mi><mi>d</mi><mi>t</mi></mrow></semantics></math></inline-formula>) on the studied objectives in three types of due windows (common, slack and different due windows). This serves to minimize the weighted sum of earliness, tardiness, starting time and size of due window, where the weights (coefficients) are related to the location. Through the theoretical analysis of the optimal solution, it is found that these three problems can be solved in time <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><mi>N</mi><mi>log</mi><mi>N</mi><mo>)</mo></mrow></semantics></math></inline-formula>, respectively, where <i>N</i> is the number of jobs.
|
|---|