Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect Function
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 t...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2021/9236044 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832556522924670976 |
|---|---|
| author | Kunping Shen Yuke Chen Shangchia Liu |
| author_facet | Kunping Shen Yuke Chen Shangchia Liu |
| author_sort | Kunping Shen |
| collection | DOAJ |
| description | 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<a1≤1. Finally, we show that the sum of the weighted completion problem and the maximum lateness problem have polynomial-time solutions for a1>M under some agreeable conditions, respectively. |
| format | Article |
| id | doaj-art-acb1b24e837647d18483734b39bd8154 |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-acb1b24e837647d18483734b39bd81542025-02-03T05:45:10ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2021-01-01202110.1155/2021/92360449236044Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect FunctionKunping Shen0Yuke Chen1Shangchia Liu2Department of Business, Chongqing City Management College, Chongqing 401331, ChinaSchool of Economics and Management, Chongqing Normal University, Chongqing 401331, ChinaDepartment of Business Administration, Fu Jen Catholic University, New Taipei City, TaiwanThis 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<a1≤1. Finally, we show that the sum of the weighted completion problem and the maximum lateness problem have polynomial-time solutions for a1>M under some agreeable conditions, respectively.http://dx.doi.org/10.1155/2021/9236044 |
| spellingShingle | Kunping Shen Yuke Chen Shangchia Liu Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect Function Discrete Dynamics in Nature and Society |
| title | Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect Function |
| title_full | Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect Function |
| title_fullStr | Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect Function |
| title_full_unstemmed | Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect Function |
| title_short | Single-Machine Scheduling Problems with the General Sum-of-Processing-Time and Position-Dependent Effect Function |
| title_sort | single machine scheduling problems with the general sum of processing time and position dependent effect function |
| url | http://dx.doi.org/10.1155/2021/9236044 |
| work_keys_str_mv | AT kunpingshen singlemachineschedulingproblemswiththegeneralsumofprocessingtimeandpositiondependenteffectfunction AT yukechen singlemachineschedulingproblemswiththegeneralsumofprocessingtimeandpositiondependenteffectfunction AT shangchialiu singlemachineschedulingproblemswiththegeneralsumofprocessingtimeandpositiondependenteffectfunction |