Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect Function

Kunping Shen, Yuke Chen, Shangchia Liu and Juan L. G. Guirao

Discrete Dynamics in Nature and Society, 2021, vol. 2021, 1-11

Abstract: This paper considers the combination of the general sum-of-processing-time effect and position-dependent effect on a single machine. The actual processing time of a job is defined by functions of the sum of the normal processing times of the jobs processed and its position and control parameter in the sequence. We consider two monotonic effect functions: the nondecreasing function and the nonincreasing function. Our focus is the following objective functions, including the makespan, the sum of the completion time, the sum of the weighted completion time, and the maximum lateness. For the nonincreasing effect function, polynomial algorithm is presented for the makespan problem and the sum of completion time problem, respectively. The latter two objective functions can also be solved in polynomial time if the weight or due date and the normal processing time satisfy some agreeable relations. For the nondecreasing effect function, assume that the given parameter is zero. We also show that the makespan problem can remain polynomially solvable. For the sum of the total completion time problem and a1 is the deteriorating rate of the jobs, there exists an optimal solution for a1≥M; a V-shaped property with respect to the normal processing times is obtained for 0 M under some agreeable conditions, respectively.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/ddns/2021/9236044.pdf (application/pdf)
http://downloads.hindawi.com/journals/ddns/2021/9236044.xml (application/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnddns:9236044

DOI: 10.1155/2021/9236044

Access Statistics for this article

More articles in Discrete Dynamics in Nature and Society from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().