Photo by szolkin from unsplash
This paper investigates online scheduling problems with processing set restrictions. There is a sequence of jobs that are revealed one by one over list, where each job has unit processing… Click to show full abstract
This paper investigates online scheduling problems with processing set restrictions. There is a sequence of jobs that are revealed one by one over list, where each job has unit processing time. A job can only be processed by a subset of the machines, namely the processing set of the job. The objective is to minimize the makespan. For m machines with two different processing sets, we propose an optimal algorithm with a competitive ratio of $$\frac{3}{2}$$ . For three machines with inclusive processing sets, an optimal algorithm with competitive ratio $$\frac{5}{3}$$ is provided.
Journal Title: Journal of the Operations Research Society of China
Year Published: 2019
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!