Some Scheduling Problems on a Single Machine with General Job Effects of Position-Dependent Learning and Start-Time-Dependent Deterioration

Jan-Yee Kung () and Ming-Hung Shu ()
Additional contact information
Jan-Yee Kung: Department of Business Administration, Cheng Shiu University, Kaohsiung, Taiwan
Ming-Hung Shu: Department of Industrial Engineering and Management, National Kaohsiung University of Applied Sciences, Kaohsiung, Taiwan

Asia-Pacific Journal of Operational Research (APJOR), 2015, vol. 32, issue 02, 1-21

Abstract: Job learning and deterioration coexist in many realistic machine-job scheduling situations. However, in literature, the constructed forms of the machine scheduling models with job learning and/or deteriorating effects were specific types of functions, which constrained their applicability in practice. This paper introduces a new single-machine scheduling model, where the actual processing time of a job is a general function of its starting time as well as scheduled position, which shows a broad generalization in contrast to that of certain existing models. For three objectives corresponding to the single-machine scheduling problem–total weighted completion time, discounted total weighted completion time, and maximum lateness — this paper presents their respective approximation result on the basis of the worst-case bound analysis from the optimal algorithm. The results demonstrate that under our proposed model, minimization of scheduling operations such as the makespan, sum of the kth power of completion times, and total lateness are polynomially solvable. Moreover, under some feasible conditions for the scheduling parameters, the minimum optimization problems of the total weighted completion time, discounted total weighted completion time, maximum lateness, and total tardiness are all recognized as polynomial forms and their solutions are provided.

Keywords: Scheduling; single machine; learning effect; job deterioration; heuristic algorithm (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595915500025
Access to full text is restricted to subscribers

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:wsi:apjorx:v:32:y:2015:i:02:n:s0217595915500025

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595915500025

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().