Open AccessSingle Machine Scheduling Problem with Controllable Setup and Job Processing Times and Position-Dependent Workloads
Author(s) -
Chengxin Luo,
Geng Zhang
Publication year - 2020
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/790/1/012093
Subject(s) - job shop scheduling , workload , computer science , scheduling (production processes) , time complexity , position (finance) , mathematical optimization , single machine scheduling , job scheduler , distributed computing , real time computing , sequence (biology) , algorithm , mathematics , embedded system , computer network , operating system , finance , queue , economics , routing (electronic design automation) , biology , genetics
This paper concerns with a single-machine scheduling problem in which each job has a setup before being processed, the setup time and the processing time of jobs are controllable by allocating a continuously nonrenewable resource, respectively. This is different from that of [13], in which a job only has a processing time, but without a setup time. We assume that each setup and processing time of jobs has a workload that is both job and position-dependent. In the problem investigated, the total amount of resource for setup and processing times does not exceed an up bound, respectively. The objective is to determine the setup sequence, the job sequence and the resource allocation scheme to minimize makespan. We show that the problem can be solved in polynomial time and present an optimal algorithm.