NDLI: Job Shop Scheduling with Two Jobs and Nonregular Objective Functions

Please wait, while we are loading the content...

Job Shop Scheduling with Two Jobs and Nonregular Objective Functions

Content Provider	Semantic Scholar
Author	Agnetis, Alessandro Mirchandani, Pitu B. Pacciarelli, Dario Pacifici, Andrea
Copyright Year	2001
Abstract	We consider the job shop scheduling problem with tvm jobs. We consider a broad class of non-regular, quasi-convex functions of the completion time of the two jobs. We show that the optimal solution, for this class of objective functions, can be computed in O(rlogr + logH) time, where r is the number of operation pairs using the same machine, and H is the maximum operation processing time. This paper deals with the job shop problem when two jobs have to be performed in the shop. The most efficient solution algorithm for this problem is Brucker's algorithm (4), which addresses the case in which the objective is the minimization of the makespan. Sotskov (7) has given a polynomial algorithm for the more general case in which one wants to minimize an arbitrary regular (i.e., nondecreasing) objective function in the completion times of the two jobs. In this paper we extend this analysis to include quasi-convex, nonregular objective functions. Unlike classical results on the job shop with two jobs, the optimal schedule may not be semi-active. Both the sum and the maximum of these two objective functions are considered as performance criteria. Our approach consists in first finding a set of nondominated solutions, i.e., schedules which are Paretooptimal from the viewpoint of the two jobs, and then searching for an overall optimum among these solutions. Both steps are carried out in polynomial time, as long as all processing times are integers.
Starting Page	227
Ending Page	244
Page Count	18
File Format	PDF HTM / HTML
DOI	10.1080/03155986.2001.11732439
Volume Number	39
Alternate Webpage(s)	http://www.inf.uniroma3.it/wp-content/uploads/2015/04/2000-49.pdf
Alternate Webpage(s)	http://web.dia.uniroma3.it/research/2000-49.pdf
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in